Skip to main content

Research Repository

Advanced Search

Colouring (Pr+Ps)-free graphs

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

Colouring (Pr+Ps)-free graphs Thumbnail


Authors

T. Klimošová

J. Malík

T. Masařík

J. Novotná

V. Slívová



Contributors

Wen-Lian Hsu
Editor

Der-Tsai Lee
Editor

Chung-Shou Liao
Editor

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). Colouring (Pr+Ps)-free graphs. In W. Hsu, D. Lee, & C. Liao (Eds.), 29th International Symposium on Algorithms and Computation (ISAAC 2018) (5:1-5:13). https://doi.org/10.4230/lipics.isaac.2018.5

Conference Name 29th International Symposium on Algorithms and Computation (ISAAC 2018).
Conference Location Jiaoxi, Yilan County, Taiwan
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 Mar 29, 2024
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

Files






You might also like



Downloadable Citations