Hell, Pavol; Huang, Shenwei Complexity of coloring graphs without paths and cycles. (English) Zbl 1405.68140 Pardo, Alberto (ed.) et al., LATIN 2014: theoretical informatics. 11th Latin American symposium, Montevideo, Uruguay, March 31 – April 4, 2014. Proceedings. Berlin: Springer (ISBN 978-3-642-54422-4/pbk). Lecture Notes in Computer Science 8392, 538-549 (2014). 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. It has been shown by P. A. Golovach et al. [Discrete Appl. Math. 167, 107–120 (2014; Zbl 1284.05098)] that when \(\ell = 4\) all these problems can be solved in polynomial time. By contrast, we show that in most other cases the \(k\)-COLORING problem for \((P _{t },C _{\ell })\)-free graphs is NP-complete. Specifically, for \(\ell = 5\) we show that \(k\)-COLORING is NP-complete for \((P _{t },C _{5})\)-free graphs when \(k \geq 4\) and \(t \geq 7\); for \(\ell \geq 6\) we show that \(k\)-COLORING is NP-complete for \((P _{t }, C _{\ell })\)-free graphs when \(k \geq 5\), \(t \geq 6\); and additionally, we prove that 4-COLORING is NP-complete for \((P _{t },C _{\ell })\)-free graphs when \(t \geq 7\) and \(\ell \geq 6\) with \(\ell \neq 7\), and that 4-COLORING is NP-complete for \((P _{t },C _{\ell })\)-free graphs when \(t \geq 9\) and \(\ell \geq 6\) with \(\ell \neq 9\). It is known that, generally speaking, for large \(k\) the \(k\)-COLORING problem tends to remain NP-complete when one forbids an induced path \(P _{t }\) with large \(t\). Our findings mean that forbidding an additional induced cycle \(C _{\ell }\) (with \(\ell > 4)\) does not help. We also revisit the problem of \(k\)-COLORING \((P _{t },C _{4})\)-free graphs, in the case \(t = 6\). (For \(t = 5\) the \(k\)-COLORING problem is known to be polynomial even on just \(P _{5}\)-free graphs, for every \(k\).) The algorithms of Golovach et al. [loc. cit.] are not practical as they depend on Ramsey-type results, and end up using tree-decompositions with very high widths. We develop more practical algorithms for 3-COLORING and 4-COLORING on \((P _{6},C _{4})\)-free graphs. Our algorithms run in linear time if a clique cutset decomposition of the input graph is given. Moreover, our algorithms are certifying algorithms. We provide a finite list of all minimal non-\(k\)-colorable \((P _{6},C _{4})\)-free graphs, for \(k = 3\) and \(k = 4\). Our algorithms output one of these minimal obstructions whenever a \(k\)-coloring is not found. In fact, we prove that there are only finitely many minimal non-\(k\)-colorable \((P _{6},C _{4})\)-free graphs for any fixed \(k\); however, we do not have the explicit lists for higher \(k\), and thus no certifying algorithms. (We note there are infinitely many non-\(k\)-colorable \(P _{5}\)-free, and hence \(P _{6}\)-free, graphs for any given \(k \geq 4\), according to a result of Hoàng, Moore, Recoskie, Sawada, and Vatshelle.)For the entire collection see [Zbl 1284.68026]. Cited in 2 ReviewsCited in 5 Documents MSC: 68Q25 Analysis of algorithms and problem complexity 05C15 Coloring of graphs and hypergraphs 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) Citations:Zbl 1284.05098 PDFBibTeX XMLCite \textit{P. Hell} and \textit{S. Huang}, Lect. Notes Comput. Sci. 8392, 538--549 (2014; Zbl 1405.68140) Full Text: DOI arXiv