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 (Pr + Ps)-free graphs.

Klimošová, T. and Malík, J. and Masařík, T. and Novotná, J. and Paulusma, D.l and Slívová, V. (2020) 'Colouring (Pr + Ps)-free graphs.', Algorithmica., 82 (7). pp. 1833-1858.


The k-Colouring problem is to decide if the vertices of a graph can be coloured with at most k colours for a fixed integer k such that no two adjacent vertices are coloured alike. If each vertex u must be assigned a colour from a prescribed list L(u)⊆{1,…,k}, then we obtain the List k-Colouring problem. A graph G is H-free if G does not contain H as an induced subgraph. We continue an extensive study into the complexity of these two problems for H-free graphs. The graph Pr+Ps is the disjoint union of the r-vertex path Pr and the s-vertex path Ps. We prove that List 3-Colouring is polynomial-time solvable for (P2+P5)-free graphs and for (P3+P4)-free graphs. Combining our results with known results yields complete complexity classifications of 3-Colouring and List 3-Colouring on H-free graphs for all graphs H up to seven vertices.

Item Type:Article
Full text:(VoR) Version of Record
Available under License - Creative Commons Attribution.
Download PDF (Advance online version)
Full text:(VoR) Version of Record
Available under License - Creative Commons Attribution.
Download PDF
Publisher Web site:
Publisher statement:This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit licenses/by/4.0/.
Date accepted:07 January 2020
Date deposited:28 January 2020
Date of first online publication:25 January 2020
Date first made open access:28 January 2020

Save or Share this output

Look up in GoogleScholar