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



Abstract

The complexity of Colouring is fully understood for H-free graphs, but there are still major complexity gaps if two induced subgraphs and are forbidden. Let be the s-vertex cycle and be the t-vertex path . We show that Colouring is polynomial-time solvable for and , strengthening several known results. Our main approach is to initiate a study into the boundedness of the clique-width of atoms (graphs with no clique cutset) of a hereditary graph class. As a complementary result we prove that Colouring is NP-complete for and , which is the first hardness result on Colouring for -free graphs. Combining our new results with known results leads to an almost complete dichotomy for Colouring restricted to -free graphs.

Citation

Gaspers, S., Huang, S., & Paulusma, D. (2019). Colouring Square-Free Graphs without Long Induced Paths. Journal of Computer and System Sciences, 106, 60-79. https://doi.org/10.1016/j.jcss.2019.06.002

Journal Article Type Article
Acceptance Date Jun 22, 2019
Online Publication Date Jun 28, 2019
Publication Date Dec 31, 2019
Deposit Date Jul 2, 2019
Publicly Available Date Mar 28, 2024
Journal Journal of Computer and System Sciences
Print ISSN 0022-0000
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 106
Pages 60-79
DOI https://doi.org/10.1016/j.jcss.2019.06.002
Public URL https://durham-repository.worktribe.com/output/1293122

Files





You might also like



Downloadable Citations