An intractability result for the vertex 3-colourability problem
Tóm tắt
The vertex 3-colourability problem is to decide whether the vertex set of a given graph can be split into three subsets of pairwise non-adjacent vertices. This problem is known to be NP-complete in a certain class of graphs, defined by an explicit description of allowed 5-vertex induced subgraphs in them. In the present paper, we improve this result by showing that the vertex 3-colourability problem remains NP-complete for a reduced set of allowed 5-vertex induced structures. It gives a step towards obtaining a complete complexity dichotomy for the mentioned problem and all the classes, defined by 5-vertex forbidden induced prohibitions.
Tài liệu tham khảo
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 38, 779–801 (2018)
Broersma, H.J., Golovach, P.A., Paulusma, D., Song, J.: Updating the complexity status of coloring graphs without a fixed induced linear forest. Theoret. Comput. Sci. 414, 9–19 (2012)
Dailey, D.P.: Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete. Discret. Math. 30, 289–293 (1980)
Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman and Co., New York (1979)
Golovach, P.A., Paulusma, D., Song, J.: 4-coloring \(H\)-free graphs when \(H\) is small. Discret. Appl. Math. 161, 140–150 (2013)
Golovach, P., Paulusma, D., Ries, B.: Coloring graphs characterized by a forbidden subgraph. Discret. Appl. Math. 180, 101–110 (2015)
Golovach, P., Johnson, M., Paulusma, D., Song, J.: A survey on the computational complexity of coloring graphs with forbidden subgraphs. J. Graph Theory 84, 331–363 (2017)
Hell, P., Huang, S.: Complexity of coloring graphs without paths and cycles. Discret. Appl. Math. 216, 211–232 (2017)
Hoàng, C., Kamiński, M., Lozin, V.V., Sawada, J., Shu, X.: \(k\)-colorability of \(P_5\)-free graphs in polynomial time. Algorithmica 57, 74–81 (2010)
Huang, S.: Improved complexity results on \(k\)-coloring \(P_t\)-free graphs. Eur. J. Comb. 51, 336–346 (2016)
Malyshev, D.: The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs. Discret. Math. 338, 1860–1865 (2015)
Malyshev, D.: The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs. Graphs Comb. 33, 1009–1022 (2017)
Malyshev, D.: A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions. Zhurnal Srednevolzhskogo matematicheskogo obshchestva 22, 38–47 (2020). ((in Russian))
Sirotkin, D., Malyshev, D.: On the complexity of the vertex 3-coloring problem for the hereditary graph classes with forbidden subgraphs of small size. J. Appl. Ind. Math. 25, 759–769 (2018)
Spirkl, S., Chudnovsky, M., Zhong, M.: Four-coloring \(P_6\)-free graphs. In: Simposium on discrete algorithims, pp. 1239–1256 (2019)