Article ID Journal Published Year Pages File Type
6423517 Discrete Mathematics 2012 7 Pages PDF
Abstract

Let G be a graph with circular chromatic number χc(G)=kq. Given P⊆V(G) where each component of G[P] is isomorphic to the circular clique Gk,q, suppose the vertices of P have been precoloured with a (k′,q′)-colouring. We examine under what conditions one can be assured the precolouring extends to the entire graph. We study sufficient conditions based on k′q′−kq as well as the distance between precoloured components of G[P]. In particular, we examine a conjecture of Albertson and West showing the conditions for extendibility are more complex than anticipated in their work.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,