Colouring Square-Free Graphs without Long Induced Paths

VCLA hosted a talk by Daniel Paulusma

ABSTRACT

The Colouring problem is to decide if the vertices of a graph can be coloured with at most k colours for a given integer k, such that no two adjacent vertices are coloured alike. The complexity of Colouring is fully understood for graph classes characterized by one forbidden induced subgraph H, but there are still major complexity gaps if the number of colours k is fixed or if two induced subgraphs H_1 and H_2 are forbidden. We survey known results in both directions and discuss a number of new results for the second direction. Let H_1 be the s-vertex cycle C_s and H_2 be the t-vertex path P_t.  We consider the complexity of Colouring for (C_s,P_t)-free graphs. In particular we show that Colouring is polynomial-time solvable for (C_4,P_6)-free graphs and NP-complete for (C_4,P_9)-free graphs. In our talk we focus on the graph colouring techniques behind the polynomial-time result (which have a wider applicability).

Daniel Paulusma, Durham University