| Abstract: | 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) ≤ 2k. This bound is also sharp: for each ? < 0, there is a k‐degenerate graph G with χc, l(G) ≥ 2k ? ?. 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 |
