Three-coloring and list three-coloring of graphs without induced paths on seven vertices (Q1786047)

A graph \(G\) is \(H\)-free if \(G\) does not contain an induced subgraph isomorphic to \(H\). It is known that if \(H\) contains a cycle, then \(k\) -coloring is NP-complete for \(k\geq 3\) for the class of \(H\)-free graphs. In contrast, it is proved in this paper that one can decide whether a given \(P_{7}\)-free graph has a \(3\)-coloring and can find such a coloring, if any, in polynomial time.