T. Klimošová
Colouring (Pr+Ps)-free graphs
Klimošová, T.; Malík, J.; Masařík, T.; Novotná, J.; Paulusma, D.; Slívová, V.
Authors
J. Malík
T. Masařík
J. Novotná
Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
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 | 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 |
Files
Published Conference Proceeding
(484 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Accepted Conference Proceeding
(550 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Copyright Statement
© Tereza Klimošová, Josef Malík, Tomáš Masařík, Jana Novotná, Daniël Paulusma, Veronika Slívová; licensed under Creative Commons License CC-BY.
You might also like
Matching cuts in graphs of high girth and H-free graphs
(2023)
Conference Proceeding
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2023)
Journal Article
Computing Subset Vertex Covers in H-Free Graphs
(2023)
Conference Proceeding
Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius
(2023)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search