Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

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

Huang, S. and Johnson, Matthew and Paulusma, Daniel (2015) 'Narrowing the complexity gap for colouring (Cs, Pt)-free graphs.', The computer journal., 58 (11). pp. 3074-3088.

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.

Item Type:Article
Keywords:Graph colouring, Forbidden induced subgraph, Computational complexity, List colouring, Precolouring extension.
Full text:(AM) Accepted Manuscript
Download PDF
(225Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1093/comjnl/bxv039
Publisher 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.
Date accepted:30 April 2015
Date deposited:09 November 2015
Date of first online publication:November 2015
Date first made open access:08 June 2016

Save or Share this output

Export:
Export
Look up in GoogleScholar