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. and Slívová, V. (2018) 'Colouring (Pr+Ps)-free graphs.', in 29th International Symposium on Algorithms and Computation (ISAAC 2018). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 5:1-5:13. Leibniz international proceedings in informatics. (123).


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) subseteq {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. We prove that List 3-Colouring is polynomial-time solvable for (P_2+P_5)-free graphs and for (P_3+P_4)-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. We also prove that 5-Colouring is NP-complete for (P_3+P_5)-free graphs.

Item Type:Book chapter
Full text:(VoR) Version of Record
Available under License - Creative Commons Attribution.
Download PDF
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution.
Download PDF
Publisher Web site:
Publisher statement:© Tereza Klimošová, Josef Malík, Tomáš Masařík, Jana Novotná, Daniël Paulusma, Veronika Slívová; licensed under Creative Commons License CC-BY.
Date accepted:31 August 2018
Date deposited:11 September 2018
Date of first online publication:27 November 2018
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar