Narrowing the Complexity Gap for Colouring (Cs, Pt)-Free Graphs
Shenwei Huang, Matthew Johnson, Daniël Paulusma · The Computer Journal · 2015
For a positive integer |$k$| and graph |$G=(V,E)$|, a |$k$|-colouring of |$G$| is a mapping |$c: V\rightarrow \{1,2,\ldots ,k\}$| such that |$c(u) eq c(v)$| whenever |$uv\in 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,\ldots ,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.