Colouring square-free graphs without long induced paths

摘要

The complexity of Colouring is fully understood for H-free graphs, but there are still major complexity gaps if two induced subgraphs H1 and H2 are forbidden. Let H1 be the s-vertex cycle Cs and H2 be the t-vertex path Pt. We show that Colouring is polynomial-time solvable for s=4 and t≤6, strengthening several known results. Our main approach is to initiate a study into the boundedness of the clique-width of atoms (graphs with no clique cutset) of a hereditary graph class. As a complementary result we prove that Colouring is NP-complete for s=4 and t≥9, which is the first hardness result on Colouring for (C4,Pt)-free graphs. Combining our new results with known results leads to an almost complete dichotomy for Colouring restricted to (Cs,Pt)-free graphs.