Circular choosability of graphs

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