Colouring (Pr+Ps)-free graphs

Klimošová, T.; Malík, J.; Masařík, T.; Novotná, J.; Paulusma, D.; Slívová, V.

Abstract

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.

Citation

Klimošová, T., Malík, J., Masařík, T., Novotná, J., Paulusma, D., & Slívová, V. (2018, December). Colouring (Pr+Ps)-free graphs. Presented at 29th International Symposium on Algorithms and Computation (ISAAC 2018)., Jiaoxi, Yilan County, Taiwan

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 29th International Symposium on Algorithms and Computation (ISAAC 2018).
• Start Date: Dec 16, 2018
• End Date: Dec 19, 2018
• Acceptance Date: Aug 31, 2018
• Online Publication Date: Nov 27, 2018
• Publication Date: Nov 1, 2018
• Deposit Date: Sep 10, 2018
• Publicly Available Date: Jun 12, 2019
• Pages: 5:1-5:13
• Series Title: Leibniz international proceedings in informatics
• Series Number: 123
• Series ISSN: 1868-8969
• Book Title: 29th International Symposium on Algorithms and Computation (ISAAC 2018).
• DOI: https://doi.org/10.4230/lipics.isaac.2018.5
• Public URL: https://durham-repository.worktribe.com/output/1143624