Colouring (Pr + Ps)-Free Graphs.

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. [ABSTRACT FROM AUTHOR]