Klimošová, T. and Malík, J. and Masařík, T. and Novotná, J. and Paulusma, D.l and Slívová, V. (2020) 'Colouring (Pr + Ps)-free graphs.', Algorithmica., 82 (7). pp. 1833-1858.
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.
| Item Type: | Article |
|---|---|
| Full text: | (VoR) Version of Record Available under License - Creative Commons Attribution. Download PDF (Advance online version) (4276Kb) |
| Full text: | (VoR) Version of Record Available under License - Creative Commons Attribution. Download PDF (4258Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | https://doi.org/10.1007/s00453-020-00675-w |
| Publisher statement: | 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/. |
| Date accepted: | 07 January 2020 |
| Date deposited: | 28 January 2020 |
| Date of first online publication: | 25 January 2020 |
| Date first made open access: | 28 January 2020 |
Save or Share this output
| Export: | |
| Look up in GoogleScholar |
