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.l; Slívová, V.

Colouring (Pr + Ps)-Free Graphs Thumbnail


Authors

T. Klimošová

J. Malík

T. Masařík

J. Novotná

V. Slívová



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 Mar 28, 2024
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

Files

Published Journal Article (Advance online version) (4.4 Mb)
PDF

Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/

Copyright Statement
Advance online version 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 http://creativecommons.org/
licenses/by/4.0/.






You might also like



Downloadable Citations