The complexity of coloring graphs without long induced paths (Q2770587)

A graph \(G=(V,E)\) is \(k\)-colorable if there exists a coloring \(f : V \to \{1, \ldots , k\}\) such that \(f(u) \neq f(v)\) for every edge \([u,v] \in E\). The chromatic number \(\chi(G)\) of graph \(G\) is the smallest \(k\) for which \(G\) is \(k\)-colorable. A graph \(G=(V,E)\) is \(P_{m}\)-free if it does not contain the path \(P_{m}\) on \(m\) vertices as an induced subgraph. For \(v \in V\), let \(\Gamma (v) =\{ w \in V : [v,w] \in V \}\) be the neighborhood of \(v\) and for \(W \subseteq V\) let \(\Gamma(W) = \bigcup_{w \in W} \Gamma(w)\). The authors discuss the computational complexity of determining the chromatic number of graphs without long induced paths. They prove the NP-completeness of deciding whether a \(P_{8}\)-free graph is 5-colorable and of deciding whether a \(P_{12}\)-free graph is 4-colorable. Moreover, they give a polynomial time algorithm for deciding whether a \(P_{5}\)-free graph is 3-colorable.