4-coloring \(H\)-free graphs when \(H\) is small (Q1759872)

The paper determines the computational complexity of \(4\)-colouring \(H\)-free graphs where \(H\) is a graph on at most five vertices. The \(k\)-colouring problem is to decide whether a given graph has a \(k\)-colouring. Here \(k\) is fixed, that is, it is not part of the input. The \(k\)-colouring problem is \(NP\)-complete for any fixed \(k \geq 3\); however, the problem is polynomial-time solvable when restricted to certain graph classes. A graph is said to be \(H\)-free if it contains no induced subgraph isomorphic to \(H\). \textit{V. V. Lozin} and \textit{M. Kamiński} [Contrib. Discrete Math. 2, No. 1, 61--66 (2007; Zbl 1188.05065)] proved that, for \(k \geq 3\), the \(k\)-colouring problem is \(NP\)-complete for the class of \(H\)-free graphs whenever \(H\) contains a cycle, while \textit{D. Leven} and \textit{Z. Galil} [J.\ Algorithms 4, 35--44 (1983; Zbl 0509.68037)] proved that the same conclusion holds whenever \(H\) is a forest with a vertex of degree at least three. This leaves the question of the computational complexity of the \(k\)-colouring problem when restricted to \(H\)-free graphs where \(H\)-is a linear forest, that is, a disjoint union of paths. Through a series of previous papers, it has been proved that, for any graph \(H\) on at most six vertices, the \(3\)-colouring problem is polynomial-time solvable on \(H\)-free graphs whenever \(H\) is a linear forest, and \(NP\)-complete otherwise. In the paper under review it is proved that, for any fixed graph \(H\) on at most five vertices, the \(5\)-colouring problem is polynomial-time solvable on \(H\)-free graphs whenever \(H\) is a linear forest, and \(NP\)-complete otherwise.