> Detailanzeige

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

Colouring (P_r+P_s)-Free Graphs

Literatur-
verwaltung

Zur
Merkliste

Lösche von
Merkliste

Per Whatsapp teilen

Schließen

Merkliste



Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
  • Medientyp: Elektronischer Konferenzbericht; E-Artikel; Sonstige Veröffentlichung
  • Titel: Colouring (P_r+P_s)-Free Graphs
  • Beteiligte: Klimosová, Tereza [VerfasserIn]; Malík, Josef [VerfasserIn]; Masarík, Tomás [VerfasserIn]; Novotná, Jana [VerfasserIn]; Paulusma, Daniël [VerfasserIn]; Slívová, Veronika [VerfasserIn]
  • Erschienen: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018
  • Sprache: Englisch
  • DOI: https://doi.org/10.4230/LIPIcs.ISAAC.2018.5
  • Schlagwörter: linear forest ; vertex colouring ; H-free graph
  • Entstehung:
  • Anmerkungen: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
  • Beschreibung: 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.
  • Zugangsstatus: Freier Zugang