Narrowing the complexity gap for colouring (Cs, Pt)-free graphs

Huang, S.; Johnson, M.; Paulusma, D.

doi:10.1093/comjnl/bxv039

Narrowing the complexity gap for colouring (Cs, Pt)-free graphs

Huang, S.; Johnson, M.; Paulusma, D.

Authors

S. Huang

Professor Matthew Johnson matthew.johnson2@durham.ac.uk
Head Of Department

Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor

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.

Citation

Huang, S., Johnson, M., & Paulusma, D. (2015). Narrowing the complexity gap for colouring (Cs, Pt)-free graphs. The Computer Journal, 58(11), 3074-3088. https://doi.org/10.1093/comjnl/bxv039

Journal Article Type	Article
Acceptance Date	Apr 30, 2015
Publication Date	Nov 1, 2015
Deposit Date	Oct 31, 2015
Publicly Available Date	Jun 8, 2016
Journal	The Computer Journal
Print ISSN	0010-4620
Electronic ISSN	1460-2067
Publisher	BCS, The Chartered Institute for IT
Peer Reviewed	Peer Reviewed
Volume	58
Issue	11
Pages	3074-3088
DOI	https://doi.org/10.1093/comjnl/bxv039
Keywords	Graph colouring, Forbidden induced subgraph, Computational complexity, List colouring, Precolouring extension.

Files

Accepted Journal Article (230 Kb)
PDF

Copyright Statement
This is a pre-copyedited, author-produced PDF of an article accepted for publication in The Computer Journal following peer review. The version of record Huang, S., Johnson, Matthew and Paulusma, Daniel (2015) 'Narrowing the complexity gap for colouring (Cs, Pt)-free graphs.', The computer journal., 58 (11): 3074-3088 is available online at: http://dx.doi.org/10.1093/comjnl/bxv039.