> Details

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

Colouring (P_r+P_s)-Free Graphs

Reference
management

Bookmarks

Remove from
bookmarks

Share this on Whatsapp

Close

Bookmarks



You can manage bookmarks using lists, please log in to your user account for this.
  • Media type: Text; E-Article; Electronic Conference Proceeding
  • Title: Colouring (P_r+P_s)-Free Graphs
  • Contributor: Klimosová, Tereza [Author]; Malík, Josef [Author]; Masarík, Tomás [Author]; Novotná, Jana [Author]; Paulusma, Daniël [Author]; Slívová, Veronika [Author]
  • imprint: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018
  • Language: English
  • DOI: https://doi.org/10.4230/LIPIcs.ISAAC.2018.5
  • Keywords: H-free graph ; vertex colouring ; linear forest
  • Origination:
  • Footnote: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
  • Description: 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.
  • Access State: Open Access