@article { ,
title = {Narrowing the complexity gap for colouring (Cs, Pt)-free graphs},
abstract = {For a positive integer k and graph G=(V,E), a k-colouring of G is a mapping c:V→\{1,2,…,k\} such that c(u)≠c(v) whenever uv∈E. The k-Colouring problem is to decide, for a given G, whether a k-colouring of G exists. The k-Precolouring Extension problem is to decide, for a given G=(V,E), whether a colouring of a subset of V can be extended to a k-colouring of G. A k-list assignment of a graph is an allocation of a list—a subset of \{1,…,k\}—to each vertex, and the List k-Colouring problem is to decide, for a given G, whether G has a k-colouring in which each vertex is coloured with a colour from its list. We consider the computational complexity of these three decision problems when restricted to graphs that do not contain a cycle on s vertices or a path on t vertices as induced subgraphs (for fixed positive integers s and t). We report on past work and prove a number of new NP-completeness results.},
doi = {10.1093/comjnl/bxv039},
eissn = {1460-2067},
issn = {0010-4620},
issue = {11},
journal = {The Computer Journal},
note = {EPrint Processing Status: Full text deposited in DRO},
pages = {3074-3088},
publicationstatus = {Published},
publisher = {BCS, The Chartered Institute for IT},
volume = {58},
keyword = {Algorithms and Complexity in Durham (ACiD), Graph colouring, Forbidden induced subgraph, Computational complexity, List colouring, Precolouring extension.},
year = {2015},
author = {Huang, S. and Johnson, M. and Paulusma, D.}
}