License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2018.5
URN: urn:nbn:de:0030-drops-99533
URL: https://drops.dagstuhl.de/opus/volltexte/2018/9953/
Go to the corresponding LIPIcs Volume Portal

Klimosová, Tereza ; Malík, Josef ; Masarík, Tomás ; Novotná, Jana ; Paulusma, Daniël ; Slívová, Veronika

Colouring (P_r+P_s)-Free Graphs

pdf-format:
LIPIcs-ISAAC-2018-5.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{klimosov_et_al:LIPIcs:2018:9953,
  author =	{Tereza Klimosov{\'a} and Josef Mal{\'i}k and Tom{\'a}s Masar{\'i}k and Jana Novotn{\'a} and Dani{\"e}l Paulusma and Veronika Sl{\'i}vov{\'a}},
  title =	{{Colouring (P_r+P_s)-Free Graphs}},
  booktitle =	{29th International Symposium on Algorithms and Computation  (ISAAC 2018)},
  pages =	{5:1--5:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9953},
  URN =		{urn:nbn:de:0030-drops-99533},
  doi =		{10.4230/LIPIcs.ISAAC.2018.5},
  annote =	{Keywords: vertex colouring, H-free graph, linear forest}
}

Keywords: vertex colouring, H-free graph, linear forest
Collection: 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Issue Date: 2018
Date of publication: 06.12.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI