S. Gaspers
Colouring Square-Free Graphs without Long Induced Paths
Gaspers, S.; Huang, S.; Paulusma, D.
Authors
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
Published Conference Proceeding
(510 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Copyright Statement
© Serge Gaspers, Shenwei Huang, and Daniël Paulusma; licensed under Creative Commons License CC-BY
You might also like
Matching cuts in graphs of high girth and H-free graphs
(2023)
Conference Proceeding
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2023)
Journal Article
Computing Subset Vertex Covers in H-Free Graphs
(2023)
Conference Proceeding
Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius
(2023)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search