Gaspers, S. and Huang, S. and Paulusma, D. (2018) 'Colouring square-free graphs without long induced paths.', in 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) : February 28–March 3, 2018, Caen, France. Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 35:1-35:15. Leibniz International Proceedings in Informatics (LIPIcs). (96).
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. Despite a huge body of existing work, there are still major complexity gaps if two induced subgraphs H_1 and H_2 are forbidden. We let H_1 be the s-vertex cycle C_s and H_2 be the t-vertex path P_t. We show that Colouring is polynomial-time solvable for s=4 and t<=6, which unifies several known results for Colouring on (H_1,H_2)-free graphs. Our algorithm is based on a novel decomposition theorem for (C_4,P_6)-free graphs without clique cutsets into homogeneous pairs of sets and a new framework for bounding the clique-width of a graph by the clique-width of its subgraphs induced by homogeneous pairs of sets. To apply this framework, we also need to use divide-and-conquer to bound the clique-width of subgraphs induced by homogeneous pairs of sets. To complement our positive result we also prove that Colouring is NP-complete for s=4 and t>=9, which is the first hardness result on Colouring for (C_4,P_t)-free graphs.
|Item Type:||Book chapter|
|Full text:||(VoR) Version of Record|
Available under License - Creative Commons Attribution.
Download PDF (498Kb)
|Publisher Web site:||http://drops.dagstuhl.de/opus/volltexte/2018/8492/|
|Publisher statement:||© Serge Gaspers, Shenwei Huang, and Daniël Paulusma; licensed under Creative Commons License CC-BY|
|Date accepted:||07 January 2018|
|Date deposited:||05 March 2018|
|Date of first online publication:||February 2018|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|