Title of article :
Extending precolourings of circular cliques
Author/Authors :
Brewster، نويسنده , , Richard C. and Noel، نويسنده , , Jonathan A.، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2012
Abstract :
Let G be a graph with circular chromatic number χ c ( G ) = k q . Given P ⊆ V ( G ) where each component of G [ P ] is isomorphic to the circular clique G k , 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 ′ − k q 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.
Keywords :
colouring extension , circular colouring
Journal title :
Discrete Mathematics
Journal title :
Discrete Mathematics