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 and are forbidden. Let be the s-vertex cycle and be the t-vertex path . We show that Colouring is polynomial-time solvable for and , 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 and , which is the first hardness result on Colouring for -free graphs. Combining our new results with known results leads to an almost complete dichotomy for Colouring restricted to -free graphs