Colouring Square-Free Graphs without Long Induced Paths

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

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: Jun 28, 2020
• Journal: Journal of Computer and System Sciences
• Print ISSN: 0022-0000
• Electronic ISSN: 1090-2724
• 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