Volume 25, No 4, 2018, P. 112-130

UDC 519.17
D. V. Sirotkin and D. S. Malyshev
On the complexity of the vertex 3-coloring problem for the hereditary graph classes with forbidden
subgraphs of small size

Abstract:
The 3-coloring problem for a given graph consists in verifying whether it is possible to divide the vertex set of the graph into three subsets of pairwise nonadjacent vertices. A complete complexity classification is known for this problem for the hereditary classes defined by triples of forbidden induced subgraphs, each on at most 5 vertices. In this article, the quadruples of forbidden induced subgraphs is under consideration, each on at most 5 vertices. For all but three corresponding hereditary classes, the computational status of the 3-coloring problem is determined. Considering two of the remaining three classes, we prove their polynomial equivalence and polynomial reducibility to the third class.
Illustr. 4, bibliogr. 20.

Keywords: 3-colorability problem, hereditary class, computational complexity.

DOI: 10.17377/daio.2018.25.617

Dmitry V. Sirotkin ^1,2
Dmitry S. Malyshev ^1,2
1. National Research University Higher School of Economics,
25/12 Bolshaya Pecherskaya St., 603155 Nizhny Novgorod, Russia
2. Lobachevsky State University of Nizhny Novgorod,
23 Gagarina Ave., 603950 Nizhny Novgorod, Russia
e-mail: dmitriy.v.sirotkin@gmail.com, dsmalyshev@rambler.ru

Received 11 April 2018
Revised 20 May 2018

References

[1] F. Bonomo, M. Chudnovsky, P. Maceli, O. Schaudt, M. Stein, and M. Zhong, Three-coloring and list three-coloring of graphs without induced paths on seven vertices, Comb., 1–23, 2018.
DOI: 10.1007/s00493-017-3553-8.

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

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

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

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

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

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

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

[9] C. Hoàng, M. Kaminski, V. V. Lozin, J. Sawada, and X. Shu, Deciding $k$-colorability of $P_5$-free graphs in polynomial time, Algorithmica, 57, 74–81, 2010.

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

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

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

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

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

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

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

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

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

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

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