2026-07-20T06:22:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6038 2024-03-06T10:37:30Z ddc:004 open_access

Colouring Diamond-free Graphs Dabrowski, Konrad K. Dross, François Paulusma, Daniël colouring clique-width diamond-free graph class hereditary graph class 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Konrad K. Dabrowski and François Dross and Daniël Paulusma 2016 Is Part Of LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2016.16 urn:nbn:de:0030-drops-60380 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.16 eng https://creativecommons.org/licenses/by/3.0/legalcode