Narrowing the Complexity Gap for Colouring (C-s, P-t)-Free Graphs

作者：Huang Shenwei; Johnson Matthew; Paulusma Daniel^*

来源：Computer Journal, 2015, 58(11): 3074-3088.

DOI：10.1093/comjnl/bxv039

• graph colouring
• forbidden induced subgraph
• computational complexity
• list colouring
• precolouring extension

For a positive integer k and graph G = (V, E), a k-colouring of G is amapping c : V ->{1, 2,..., k} such that c(u) not equal c(v) whenever uv is an element of 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.

• 出版日期2015-11