Extending precolourings of circular cliques

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...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2012-01, Vol.312 (1), p.35-41
Main Authors: Brewster, Richard C., Noel, Jonathan A.
Format: Article
Language:English
Subjects:
Circular colouring
Colouring extension
Graphs
Mathematical analysis
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2011.02.008