Abstrakt
The k-Colouring problem is to decide if the vertices of a graph can be coloured with at most k colours for a fixed integer k such that no two adjacent vertices are coloured alike. If each vertex u must be assigned a colour from a prescribed list L(u). {1,., k}, then we obtain the List k-Colouring problem.
A graph G is H-free if G does not contain H as an induced subgraph. We continue an extensive study into the complexity of these two problems for H-free graphs.
The graph P r + P s is the disjoint union of the r-vertex path P r and the s-vertex path P s. We prove that List 3-Colouring is polynomial-time solvable for (P 2 + P 5)-free graphs and for (P 3 + P 4)-free graphs.
Combining our results with known results yields complete complexity classifications of 3-Colouring and List 3-Colouring on H-free graphs for all graphs H up to seven vertices.