On colouring (2P_2, H)-free and (P_5, H)-free graphs

摘要

The COLOURING problem asks whether the vertices of a graph can be coloured with at most k colours for a given integer k in such a way that no two adjacent vertices receive the same colour. A graph is (H-1, H-2)-free if it has no induced subgraph isomorphic to H-1 or H-2. A connected graph H-1 is almost classified if COLOURING on (H-1, H-2)-free graphs is known to be polynomial-time solvable or NP-complete for all but finitely many connected graphs H-2. We show that every connected graph H-1 apart from the claw K-1,K-3 and the 5-vertex path P-5 is almost classified. We also prove a number of new hardness results for COLOURING on (2P(2), H)-free graphs. This enables us to list all graphs H for which the complexity of COLOURING is open on (2P(2), H)-free graphs and all graphs H for which the complexity of COLOURING is open on (P-5, H)-free graphs. In fact we show that these two lists coincide. Moreover, we show that the complexities of COLOURING for (2P(2), H)-free graphs and for (P-5, H)-free graphs are the same for all known cases. (C) 2018 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license.