Colouring (P_r P_s)-Free Graphs

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10385832" target="_blank" >RIV/00216208:11320/18:10385832 - isvavai.cz</a>

Alternative codes found

RIV/68407700:21240/18:00325508

Result on the web

<a href="https://doi.org/10.4230/LIPIcs.ISAAC.2018.5" target="_blank" >https://doi.org/10.4230/LIPIcs.ISAAC.2018.5</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.ISAAC.2018.5" target="_blank" >10.4230/LIPIcs.ISAAC.2018.5</a>

Result language

angličtina

Original language name

Colouring (P_r P_s)-Free Graphs

Original language 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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2018

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

29th International Symposium on Algorithms and Computation, {ISAAC} 2018, December 16-19, 2018, Jiaoxi, Yilan, Taiwan

ISBN

978-3-95977-094-1

ISSN

1868-8969

e-ISSN

neuvedeno

Number of pages

13

Pages from-to

1-13

Publisher name

Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik

Place of publication

Schloss Dagstuhl

Event location

Jiaoxi

Event date

Dec 16, 2018

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—