Colouring Square-Free Graphs without Long Induced Paths

Gaspers, S.; Huang, S.; Paulusma, D.

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. 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.

Citation

Gaspers, S., Huang, S., & Paulusma, D. (2023, February). Colouring Square-Free Graphs without Long Induced Paths. Presented at 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), Caen, France

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
• Start Date: Feb 28, 2023
• End Date: Mar 3, 2018
• Acceptance Date: Jan 7, 2018
• Publication Date: Feb 1, 2018
• Deposit Date: Mar 5, 2018
• Publicly Available Date: Mar 5, 2018
• Pages: 35:1-35:15
• Series Title: Leibniz International Proceedings in Informatics (LIPIcs)
• Series Number: 96
• Series ISSN: 1868-8969
• Book Title: 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) : February 28–March 3, 2018, Caen, France.
• DOI: https://doi.org/10.4230/lipics.stacs.2018.35
• Public URL: https://durham-repository.worktribe.com/output/1145787
• Publisher URL: http://drops.dagstuhl.de/opus/volltexte/2018/8492/