Skip to main content

Research Repository

Advanced Search

Colouring diamond-free graphs

Dabrowski, K. K.; Dross, F.; Paulusma, D.

Colouring diamond-free graphs Thumbnail


Authors

K. K. Dabrowski

F. Dross



Contributors

Rasmus Pagh
Editor

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,P_1+2P_2)-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 (H_1,H_2)-free graphs. As such, our work also continues a recent systematic study into the (un)boundedness of clique-width of (H_1,H_2)-free graphs, and our five new classes of bounded clique-width reduce the number of open cases from 13 to 8.

Citation

Dabrowski, K. K., Dross, F., & Paulusma, D. (2016). Colouring diamond-free graphs. In R. Pagh (Ed.), 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). https://doi.org/10.4230/lipics.swat.2016.16

Conference Name 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Conference Location Reykjavik, Iceland
Start Date Jun 22, 2016
End Date Jun 24, 2016
Acceptance Date Apr 1, 2016
Publication Date Jun 24, 2016
Deposit Date Jun 29, 2016
Publicly Available Date Jul 1, 2016
Series Title Leibniz International Proceedings in Informatics (LIPIcs)
Series Number 53
Series ISSN 1868-8969
Book Title 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016).
DOI https://doi.org/10.4230/lipics.swat.2016.16
Public URL https://durham-repository.worktribe.com/output/1150501
Additional Information Conference date: 22-24 June 2016

Files





You might also like



Downloadable Citations