Skip to main content

Research Repository

Advanced Search

Colouring Square-Free Graphs without Long Induced Paths

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

Colouring Square-Free Graphs without Long Induced Paths Thumbnail


Authors

S. Gaspers

S. Huang



Contributors

Rolf Niedermeier
Editor

Brigitte Vallée
Editor

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. (2018). Colouring Square-Free Graphs without Long Induced Paths. In R. Niedermeier, & B. Vallée (Eds.), 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) : February 28–March 3, 2018, Caen, France (35:1-35:15). https://doi.org/10.4230/lipics.stacs.2018.35

Conference Name 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Conference Location Caen, France
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/

Files





You might also like



Downloadable Citations