|
Эта публикация цитируется в 7 научных статьях (всего в 7 статьях)
О пересечении и симметрической разности семейств граничных классов для задач о раскраске и о хроматическом числе
Д. С. Малышев
Аннотация:
В работе исследуются семейства граничных классов для задач о вершинной $k$-раскраске и о хроматическом числе. Указано континуальное семейство классов графов, являющихся граничными одновременно для первой задачи при $k=3$ и для второй. Для любого $k>3$ выявлено континуальное семейство граничных классов для первой задачи, не являющихся граничными для второй. Для задачи о хроматическом числе найден граничный класс, не являющийся граничным для задачи о вершинной $k$-раскраске ни при каком $k$.
DOI:
https://doi.org/10.4213/dm1184
Полный текст:
PDF файл (85 kB)
Список литературы:
PDF файл
HTML файл
Англоязычная версия:
Discrete Mathematics and Applications, 2011, 21:5-6, 645–649
Реферативные базы данных:
Тип публикации:
Статья
УДК:
519.17 Статья поступила: 19.01.2010
Образец цитирования:
Д. С. Малышев, “О пересечении и симметрической разности семейств граничных классов для задач о раскраске и о хроматическом числе”, Дискрет. матем., 24:2 (2012), 75–78; Discrete Math. Appl., 21:5-6 (2011), 645–649
Цитирование в формате AMSBIB
\RBibitem{Mal12}
\by Д.~С.~Малышев
\paper О пересечении и симметрической разности семейств граничных классов для задач о раскраске и о хроматическом числе
\jour Дискрет. матем.
\yr 2012
\vol 24
\issue 2
\pages 75--78
\mathnet{http://mi.mathnet.ru/dm1184}
\crossref{https://doi.org/10.4213/dm1184}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3050556}
\elib{https://elibrary.ru/item.asp?id=20730425}
\transl
\jour Discrete Math. Appl.
\yr 2011
\vol 21
\issue 5-6
\pages 645--649
\crossref{https://doi.org/10.1515/dma.2011.038}
Образцы ссылок на эту страницу:
http://mi.mathnet.ru/dm1184https://doi.org/10.4213/dm1184 http://mi.mathnet.ru/rus/dm/v24/i2/p75
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
Д. С. Малышев, “Исследование граничных классов графов для задач о раскраске”, Дискретн. анализ и исслед. опер., 19:6 (2012), 37–48
; D. S. Malyshev, “Study of boundary graph classes for colorability problems”, J. Appl. Industr. Math., 7:2 (2013), 221–228 -
В. Е. Алексеев, В. А. Замараев, Д. В. Захарова, Д. С. Малышев, Д. Б. Мокеев, С. В. Сорочан, “Некоторые результаты о наследственных классах графов. III”, Вестник Нижегородского университета им. Н.И. Лобачевского, 2013, № 6-1, 165–172
-
D. S. Malyshev, “The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices”, Сиб. электрон. матем. изв., 11 (2014), 811–822
-
D. S. Malyshev, “The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs”, Discrete Math., 338:11 (2015), 1860–1865
-
D. S. Malyshev, P. M. Pardalos, “Critical hereditary graph classes: a survey”, Optim. Lett., 10:8 (2016), 1593–1612
-
D. S. Malyshev, O. O. Lobanova, “Two complexity results for the vertex coloring problem”, Discrete Appl. Math., 219 (2017), 158–166
-
V. V. Lozin, D. S. Malyshev, “Vertex coloring of graphs with few obstructions”, Discrete Appl. Math., 216:1, SI (2017), 273–280
|
Просмотров: |
Эта страница: | 303 | Полный текст: | 88 | Литература: | 42 | Первая стр.: | 21 |
|