S. Gaspers
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 | 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
Accepted Journal Article
(508 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by-nc-nd/4.0/
Copyright Statement
© 2019 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
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
An algorithmic framework for locally constrained homomorphisms
(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
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