2014/07/06 by Huang, Shenwei, Johnson, Matthew, Paulusma, Daniël · 1 citation
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1407.1480
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 continued the study of the computational complexity of these three decision problems when restricted to graphs that contain neither a cycle on s vertices nor a path on t vertices as induced subgraphs (for fixed positive integers s and~t).