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,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, June). Colouring diamond-free graphs. Presented at 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), Reykjavik, Iceland

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
• 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