The Library
Extending precolourings of circular cliques
Tools
Brewster, Richard C. and Noel, Jonathan A. (2012) Extending precolourings of circular cliques. Discrete Mathematics, 312 (1). pp. 35-41. doi:10.1016/j.disc.2011.02.008 ISSN 0012-365X.
|
PDF
WRAP-extending-precolourings-circular-cliques-Noel-2012.pdf - Accepted Version - Requires a PDF viewer. Download (473Kb) | Preview |
Official URL: http://dx.doi.org/10.1016/j.disc.2011.02.008
Abstract
Let G be a graph with circular chromatic number Xe(G) = k/q. Given P ⊆ V (G) where the components of G [P] are isomorphic to the circular clique Gk,g suppose the vertices of P have been precoloured with a (k’,g’) - colouring. We examine under what conditions one can be assured the colouring extends to the entire graph. We stud y 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.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
Library of Congress Subject Headings (LCSH): | Graph coloring | ||||||||
Journal or Publication Title: | Discrete Mathematics | ||||||||
Publisher: | Elsevier BV | ||||||||
ISSN: | 0012-365X | ||||||||
Official Date: | 6 January 2012 | ||||||||
Dates: |
|
||||||||
Volume: | 312 | ||||||||
Number: | 1 | ||||||||
Page Range: | pp. 35-41 | ||||||||
DOI: | 10.1016/j.disc.2011.02.008 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||
Date of first compliant deposit: | 10 July 2018 | ||||||||
Date of first compliant Open Access: | 10 July 2018 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year