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 atmost 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
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 (Proceedings of 27th InternationalWorkshop, Boltenhagen, Germany, June 14–16, 2001) (Springer,Heidelberg, 2001), pp. 254–262.
V. V. Lozin and D. S. Malyshev, “Vertex Coloring of Graphs with Few Obstructions,” Discrete Appl. Math. 216, 273–280 (2017).
D. S. Malyshev, “Polynomial-Time Approximation Algorithms for the Coloring Problem in Some Cases,” J. Combin. Optim. 33 (3), 809–813 (2017).
K. Dabrowski, P. A. Golovach, and D. Paulusma, “Coloring of Graphs with Ramsey-Type Forbidden Subgraphs,” Theor. Comput. Sci. 522, 34–43 (2014).
K. Dabrowski, V. V. Lozin, R. Raman, and B. Ries, “Coloring Vertices of Triangle-Free Graphs Without Forests,” DiscreteMath. 312 (7), 1372–1385 (2012).
P. A. Golovach, D. Paulusma, and B. Ries, “Coloring Graphs Characterized by a Forbidden Subgraph,” Discrete Appl. Math. 180, 101–110 (2015).
C. Hoàng and D. Lazzarato, “Polynomial-Time Algorithms for Minimum Weighted Colorings of (P5, P5)-Free Graphs and Similar Graph Classes,” Discrete Appl. Math. 186, 105–111 (2015).
D. S. Malyshev, “The Coloring Problem for Classes with Two SmallObstructions,” Optim. Lett. 8 (8), 2261–2270 (2014).
D. S. Malyshev, “Two Cases of Polynomial-Time Solvability for the Coloring Problem,” J. Combin. Optim. 31 (2), 833–845 (2015).
D. S. Malyshev and O. O. Lobanova, “Two Complexity Results for the Vertex Coloring Problem,” Discrete Appl. Math. 219, 158–166 (2017).
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 (1), 9–19 (2012).
P. A. Golovach, D. Paulusma, and J. Song, “4-Coloring H-Free Graphs when H Is Small,” Discrete Appl. Math. 161 (1–2), 140–150 (2013).
C. Hoàng, M. Kamiński, V. V. Lozin, J. Sawada, and X. Shu, “Deciding k-Colorability of P5-Free Graphs in Polynomial Time,” Algorithmica 57, 74–81 (2010).
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,” Combinatorica 1–23 (2018) [DOI: 10. 1007/s00493-017-3553-8].
S. Huang, “Improved Complexity Results on k-Coloring Pt-Free Graphs,” European J. Combin. 51, 336–346 (2016).
D. S. Malyshev, “The Complexity of the 3-Colorability Problem in the Absence of a Pair of Small Forbidden Induced Subgraphs,” DiscreteMath. 338 (11), 1860–1865 (2015).
D. S. Malyshev, “The Complexity of the Vertex 3-Colorability Problem for some Hereditary Classes Defined by 5-Vertex Forbidden Induced Subgraphs,” Graphs Combin. 33 (4), 1009–1022 (2017).
D. P. Dailey, “Uniqueness of Colorability and Colorability of Planar 4-Regular Graphs Are NP-Complete,” DiscreteMath. 30 (3), 289–293 (1980).
R. L. Brooks, “On Colouring the Nodes of a Network,” Proc. Camb. Philos. Soc. Math. Phys. Sci. 37 (2), 194–197 (1941).
V. V. Lozin and M. Kamiński, “Coloring Edges and Vertices of Graphs Without Short or Long Cycles,” Contrib. Discrete Math. 2 (1), 61–66 (2007).
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text © D.V. Sirotkin, D.S. Malyshev, 2018, published in Diskretnyi Analiz i Issledovanie Operatsii, 2018, Vol. 25, No. 4, pp. 112–130.
Rights and permissions
About this article
Cite this article
Sirotkin, D.V., Malyshev, D.S. On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size. J. Appl. Ind. Math. 12, 759–769 (2018). https://doi.org/10.1134/S1990478918040166
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S1990478918040166