K.K. Dabrowski
Colouring Diamond-free Graphs
Dabrowski, K.K.; Dross, F.; Paulusma, D.
Abstract
The Colouring problem is that of deciding, given a graph G and an integer k, whether G admits a (proper) k-colouring. For all graphs H up to five vertices, we classify the computational complexity of Colouring for (diamond,H)-free graphs. Our proof is based on combining known results together with proving that the clique-width is bounded for (diamond,P1+2P2)-free graphs. Our technique for handling this case is to reduce the graph under consideration to a k -partite graph that has a very specific decomposition. As a by-product of this general technique we are also able to prove boundedness of clique-width for four other new classes of (H1,H2)-free graphs. As such, our work also continues a recent systematic study into the (un)boundedness of clique-width of (H1,H2)-free graphs, and our five new classes of bounded clique-width reduce the number of open cases from 13 to 8.
Citation
Dabrowski, K., Dross, F., & Paulusma, D. (2017). Colouring Diamond-free Graphs. Journal of Computer and System Sciences, 89, 410-431. https://doi.org/10.1016/j.jcss.2017.06.005
Journal Article Type | Article |
---|---|
Acceptance Date | Jun 10, 2017 |
Online Publication Date | Jun 22, 2017 |
Publication Date | Nov 1, 2017 |
Deposit Date | Jun 12, 2017 |
Publicly Available Date | Jun 13, 2017 |
Journal | Journal of Computer and System Sciences |
Print ISSN | 0022-0000 |
Publisher | Elsevier |
Peer Reviewed | Peer Reviewed |
Volume | 89 |
Pages | 410-431 |
DOI | https://doi.org/10.1016/j.jcss.2017.06.005 |
Public URL | https://durham-repository.worktribe.com/output/1385307 |
Files
Accepted Journal Article
(625 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Copyright Statement
© 2017 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
Published Journal Article
(717 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
You might also like
Solving Infinite-Domain CSPs Using the Patchwork Property
(2023)
Conference Proceeding
Disjunctive Temporal Problems under Structural Restrictions
(2021)
Conference Proceeding
Fine-Grained Complexity of Temporal Problems
(2020)
Conference Proceeding
Independent transversals versus transversals
(2019)
Conference Proceeding
Filling the complexity gaps for colouring planar and bounded degree graphs
(2019)
Journal Article
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