Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Colouring diamond-free graphs.

Dabrowski, K.K. and Dross, F. and Paulusma, D. (2017) 'Colouring diamond-free graphs.', Journal of computer and system sciences., 89 . pp. 410-431.

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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution.
Download PDF
(611Kb)
Full text:(VoR) Version of Record
Available under License - Creative Commons Attribution.
Download PDF
(701Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1016/j.jcss.2017.06.005
Publisher 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/).
Date accepted:10 June 2017
Date deposited:13 June 2017
Date of first online publication:22 June 2017
Date first made open access:09 August 2017

Save or Share this output

Export:
Export
Look up in GoogleScholar