Colouring (Pr + Ps)-Free Graphs

Klimošová, T.; Malík, J.; Masařík, T.; Novotná, J.; Paulusma, D.l; 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)⊆{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.

Citation

Klimošová, T., Malík, J., Masařík, T., Novotná, J., Paulusma, D., & Slívová, V. (2020). Colouring (Pr + Ps)-Free Graphs. Algorithmica, 82(7), 1833-1858. https://doi.org/10.1007/s00453-020-00675-w

• Journal Article Type: Article
• Acceptance Date: Jan 7, 2020
• Online Publication Date: Jan 25, 2020
• Publication Date: Jul 31, 2020
• Deposit Date: Jan 27, 2020
• Publicly Available Date: Jan 28, 2020
• Journal: Algorithmica
• Print ISSN: 0178-4617
• Electronic ISSN: 1432-0541
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Volume: 82
• Issue: 7
• Pages: 1833-1858
• DOI: https://doi.org/10.1007/s00453-020-00675-w
• Public URL: https://durham-repository.worktribe.com/output/1278752