Том 25, номер 4, 2018 г., Стр. 112-130

УДК 519.17
Сироткин Д. В., Малышев Д. С.
О сложности задачи вершинной $3$-раскраски для наследственных классов графов, определённых запретами небольшого размера

Аннотация:
Задача о $3$-раскраске для заданного графа состоит в том, чтобы проверить, можно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Известна полная классификация сложности данной задачи для наследственных классов, определяемых тройками запрещённых индуцированных подграфов, каждый с не более чем $5$ вершинами. В настоящей работе рассматриваются четвёрки запрещённых индуцированных фрагментов, каждый с не более чем $5$ вершинами, и для всех соответствующих наследственных классов, кроме трёх, устанавливается вычислительный статус задачи о $3$-раскраске. Для двух из трёх оставшихся случаев доказывается полиномиальная эквивалентность и полиномиальная сводимость к третьему.
Ил. 4, библиогр. 20.

Ключевые слова: задача о $3$-раскраске, наследственный класс, вычислительная сложность.

DOI: 10.17377/daio.2018.25.617

Сироткин Дмитрий Валерьевич ^1,2
Малышев Дмитрий Сергеевич ^1,2
1. Национальный исследовательский университет «Высшая школа экономики»,
ул. Большая Печёрская, 25/12, 603155, Нижний Новгород, Россия
2. Нижегородский гос. университет им. Н. И. Лобачевского,
пр. Гагарина, 23, 603950, Нижний Новгород, Россия
е-mail: dmitriy.v.sirotkin@gmail.com, dsmalyshev@rambler.ru

Статья поступила 11 апреля 2018 г.
Исправленный вариант — 20 мая 2018 г.

Литература

[1] Bonomo F., Chudnovsky M., Maceli P., Schaudt O., Stein M., Zhong M. Three-coloring and list three-coloring of graphs without induced paths on seven vertices // Combinatorica. 2018. P. 1–23.

[2] Broersma H. J., Golovach P. A., Paulusma D., Song J. Updating the complexity status of coloring graphs without a fixed induced linear forest // Theor. Comp. Sci. 2012. Vol. 414, No. 1. P. 9–19.

[3] Brooks R. L. On colouring the nodes of a network // Proc. Camb. Philos. Soc., Math. Phys. Sci. 1941. Vol. 37, No. 2. P. 194–197.

[4] Dabrowski K., Golovach P. A., Paulusma D. Colouring of graphs with Ramsey-type forbidden subgraphs // Theor. Comput. Sci. 2014. Vol. 522. P. 34–43.

[5] Dabrowski K., Lozin V. V., Raman R., Ries B. Colouring vertices of triangle-free graphs without forests // Discrete Math. 2012. Vol. 312, No. 7. P. 1372–1385.

[6] Dailey D. P. Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete // Discrete Math. 1980. Vol. 30, No. 3. P. 289–293.

[7] Golovach P. A., Paulusma D., Ries B. Coloring graphs characterized by a forbidden subgraph // Discrete Appl. Math. 2015. Vol. 180. P. 101–110.

[8] Golovach P. A., Paulusma D., Song J. $4$-Coloring $H$-free graphs when $H$ is small // Discrete Appl. Math. 2013. Vol. 161, No. 1–2. P. 140–150.

[9] Hoàng C., Kami$\acute{n}$ski M., Lozin V. V., Sawada J., Shu X. Deciding $k$-colorability of $P_5$-free graphs in polynomial time // Algorithmica. 2010. Vol. 57. P. 74–81.

[10] Hoàng C., Lazzarato D. Polynomial-time algorithms for minimum weighted colorings of ($P_5$, $\overline{P_5}$)-free graphs and similar graph classes // Discrete Appl. Math. 2015. Vol. 186. P. 105–111.

[11] Huang S. Improved complexity results on $k$-coloring $P_t$-free graphs // Eur. J. Comb. 2016. Vol. 51. P. 336–346.

[12] Král D., Kratochvíl J., Tuza Z., Woeginger G. Complexity of coloring graphs without forbidden induced subgraphs // Graph-Theoretic Concepts in Computer Science. Proc. 27th Int. Workshop (Boltenhagen, Germany, June 14–16, 2001). Heidelberg: Springer-Verl., 2001. P. 254–262. (Lect. Notes Comput. Sci.; Vol. 2204).

[13] Lozin V. V., Kami´nski M. Coloring edges and vertices of graphs without short or long cycles // Contrib. Discrete Math. 2007. Vol. 2, No. 1. P. 61–66.

[14] Lozin V. V., Malyshev D. S. Vertex coloring of graphs with few obstructions // Discrete Appl. Math. 2017. Vol. 216. P. 273–280.

[15] Malyshev D. S. The coloring problem for classes with two small obstructions // Optim. Lett. 2014. Vol. 8, No. 8. P. 2261–2270.

[16] Malyshev D. S. The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs // Discrete Math. 2015. Vol. 338, No. 11. P. 1860–1865.

[17] Malyshev D. S. Two cases of polynomial-time solvability for the coloring problem // J. Comb. Optim. 2015. Vol. 31, No. 2. P. 833–845.

[18] Malyshev D. S. The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs // Graphs Comb. 2017. Vol. 33, No. 4. P. 1009–1022.

[19] Malyshev D. S. Polynomial-time approximation algorithms for the coloring problem in some cases // J. Comb. Optim. 2017. Vol. 33, No. 3. P. 809–813.

[20] Malyshev D. S., Lobanova O. O. Two complexity results for the vertex coloring problem // Discrete Appl. Math. 2017. Vol. 219. P. 158–166.