Hell, Pavol; Huang, Shenwei Complexity of coloring graphs without paths and cycles. (English) Zbl 1350.05037 Discrete Appl. Math. 216, Part 1, 211-232 (2017). Summary: Let \(P_t\) and \(C_\ell\) denote a path on \(t\) vertices and a cycle on \(\ell\) vertices, respectively. In this paper we study the \(k\)-coloring problem for \((P_t, C_\ell)\)-free graphs. D. Bruce et al. [Lect. Notes Comput. Sci. 5878, 594–604 (2009; Zbl 1272.05191)], and F. Maffray and G. Morel [SIAM J. Discrete Math. 26, No. 4, 1682–1708 (2012; Zbl 1261.05030)] have proved that 3-colorability of \(P_5\)-free graphs has a finite forbidden induced subgraphs characterization, while C. T. Hoàng et al. [Discrete Appl. Math. 182, 91–98 (2015; Zbl 1306.05061)] have shown that \(k\)-colorability of \(P_5\)-free graphs for \(k \geq 4\) does not. These authors have also shown, aided by a computer search, that 4-colorability of \((P_5, C_5)\)-free graphs does have a finite forbidden induced subgraph characterization. We prove that for any \(k \geq 1\), the \(k\)-colorability of \((P_6, C_4)\)-free graphs has a finite forbidden induced subgraph characterization. For \(k = 3\) and \(k = 4\), we provide the full lists of minimal forbidden induced subgraphs. As an application, we obtain certifying polynomial time algorithms for 3-coloring and 4-coloring \((P_6, C_4)\)-free graphs. (Polynomial time algorithms have been previously obtained by P. A. Golovach et al. [Discrete Appl. Math. 167, 107–120 (2014; Zbl 1284.05098)], but those algorithms are not certifying). To complement these results we show that in most other cases the \(k\)-coloring problem for \((P_t, C_\ell)\)-free graphs is NP-complete. Specifically, we prove that the \(k\)-coloring problem is NP-complete for \((P_t, C_\ell)\)-free graphs when – \(\ell = 5\), \(k \geq 4\), and \(t \geq 7\), – \(\ell \geq 6\), \(k \geq 5\), and \(t \geq 6\), – \(\ell \geq 6\) but \(\ell \neq 7\), \(k = 4\), and \(t \geq 7\), – \(\ell \geq 6\) but \(\ell \neq 9\), \(k = 4\), and \(t \geq 9\). Our results almost completely classify the complexity for the cases when \(k \geq 4\), \(\ell \geq 4\), and identify the last few open cases. Cited in 2 ReviewsCited in 21 Documents MSC: 05C15 Coloring of graphs and hypergraphs 05C38 Paths and cycles 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) Keywords:coloring; certifying algorithms; paths; cycles; NP-completeness; obstructions Citations:Zbl 1272.05191; Zbl 1261.05030; Zbl 1306.05061; Zbl 1284.05098 PDFBibTeX XMLCite \textit{P. Hell} and \textit{S. Huang}, Discrete Appl. Math. 216, Part 1, 211--232 (2017; Zbl 1350.05037) Full Text: DOI References: [1] Atminas, A.; Lozin, V. V.; Razgon, I., Linear time algorithm for computing a small biclique in graphs without long induced path, (Proceedings of SWAT 2012. Proceedings of SWAT 2012, LNCS, vol. 7357 (2012)), 142-152 · Zbl 1357.68077 [2] Bondy, J. A.; Murty, U. S.R., (Graph Theory. Graph Theory, Springer Graduate Texts in Mathematics, vol. 244 (2008)) · Zbl 1134.05001 [3] Brandstädt, A.; Hoàng, C. T., On clique separators, nearly chordal graphs, and the maximum weight stable set problem, Theoret. Comput. Sci., 389, 295-306 (2007) · Zbl 1143.68059 [4] Broersma, H. J.; Fomin, F. V.; Golovach, P. A.; Paulusma, D., Three complexity results on coloring \(P_k\)-free graphs, European J. Combin., 34, 609-619 (2013) · Zbl 1257.05037 [5] Broersma, H. J.; Golovach, P. A.; Paulusma, D.; Song, J., Updating the complexity status of coloring graphs without a fixed induced learn forest, Theoret. Comput. Sci., 414, 9-19 (2012) · Zbl 1234.68129 [10] Chudnovsky, M.; Robertson, N.; Seymour, P.; Thomas, R., The strong perfect graph theorem, Ann. of Math., 64, 51-229 (2006) · Zbl 1112.05042 [11] Erdős, P., Graph theory and probability II, Canad. J. Math., 13, 346-352 (1961) · Zbl 0097.39102 [12] Golovach, P. A.; Paulusma, D.; Song, J., Coloring graphs without short cycles and long induced paths, Discrete Appl. Math., 167, 107-120 (2014) · Zbl 1284.05098 [13] Golumbic, M. C., (Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press San Diego) · Zbl 0541.05054 [14] Grötschel, M.; Lovász, L.; Schrijver, A., Polynomial algorithms for perfect graphs, Ann. Discrete Math., 21, 325-356 (1984), Topics on perfect graphs · Zbl 0554.05041 [15] Hoàng, C. T.; Kamiński, M.; Lozin, V.; Sawada, J.; Shu, X., Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time, Algorithmica, 57, 74-81 (2010) · Zbl 1222.68083 [16] Hoàng, C. T.; Moore, B.; Recoskiez, D.; Sawada, J.; Vatshelle, M., Constructions of \(k\)-critical \(P_5\)-free graphs, Discrete Appl. Math., 182, 91-98 (2015) · Zbl 1306.05061 [17] Holyer, I., The NP-completeness of edge coloring, SIAM J. Comput., 10, 718-720 (1981) · Zbl 0473.68034 [18] Huang, S., Improved complexity results on \(k\)-coloring \(P_t\)-free graphs, (Proceedings of MFCS 2013. Proceedings of MFCS 2013, LNCS, vol. 8087 (2013)), 551-558 · Zbl 1400.68075 [19] Kamiński, M.; Lozin, V., Coloring edges and vertices of graphs without short or long cycles, Contrib. Discrete. Mah., 2, 61-66 (2007) · Zbl 1188.05065 [20] Král, D.; Kratochvíl, J.; Tuza, Zs.; Woeginger, G. J., Complexity of coloring graphs without forbidden induced subgraphs, (Proceedings of WG 2001. Proceedings of WG 2001, LNCS, vol. 2204 (2001)), 254-262 · Zbl 1042.68639 [21] Le, V. B.; Randerath, B.; Schiermeyer, I., On the complexity of 4-coloring graphs without long induced paths, Theoret. Comput. Sci., 389, 330-335 (2007) · Zbl 1143.68060 [22] Leven, D.; Galil, Z., NP-completeness of finding the chromatic index of regular graphs, J. Algorithm, 4, 35-44 (1983) · Zbl 0509.68037 [23] Maffray, F.; Morel, G., On 3-colorable \(P_5\)-free graphs, SIAM J. Discrete Math., 26, 4, 1682-1708 (2012) · Zbl 1261.05030 [24] Randerath, B.; Schiermeyer, I., 3-colorability \(\in P\) for \(P_6\)-free graphs, Discrete Appl. Math., 136, 299-313 (2004) · Zbl 1035.05042 [25] Randerath, B.; Schiermeyer, I., Vertex colouring and fibidden subgraphs-a survey, Graphs Combin., 20, 1-40 (2004) · Zbl 1056.05065 [27] Tarjan, R. E., Decomposition by clique separators, Discrete Math., 55, 221-232 (1985) · Zbl 0572.05039 [28] Tuza, Zs., Graph colorings with local restrictions-a survey, Discuss. Math. Graph Theory, 17, 161-228 (1997) · Zbl 0923.05027 [29] Woeginger, G. J.; Sgall, J., The complexity of coloring graphs without long induced paths, Acta Cybernet., 15, 107-117 (2001) · Zbl 0981.05037 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.