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



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






You might also like



Downloadable Citations