Premium
Circular choosability of graphs
Author(s) -
Zhu Xuding
Publication year - 2005
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20051
Subject(s) - combinatorics , mathematics , graph , degenerate energy levels , discrete mathematics , bound graph , list coloring , graph power , line graph , physics , quantum mechanics
This paper discusses the circular version of list coloring of graphs. We give two definitions of the circular list chromatic number (or circular choosability) χ c, l ( G ) of a graph G and prove that they are equivalent. Then we prove that for any graph G , χ c, l ( G ) ≥ χ l ( G ) − 1. Examples are given to show that this bound is sharp in the sense that for any ϵ 0, there is a graph G with χ c, l ( G ) > χ l ( G ) − 1 + ϵ. It is also proved that k ‐degenerate graphs G have χ c, l ( G ) ≤ 2 k . This bound is also sharp: for each ϵ < 0, there is a k ‐degenerate graph G with χ c, l ( G ) ≥ 2 k − ϵ. This shows that χ c, l ( G ) could be arbitrarily larger than χ l ( G ). Finally we prove that if G has maximum degree k , then χ c, l ( G ) ≤ k + 1. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 210–218, 2005