We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Computer Science


Publication details for Professor Matthew Johnson

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

Author(s) from Durham


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.