List circular coloring of trees and cycles
André Raspaud, Xuding Zhu · Journal of Graph Theory · 2007
Abstract Suppose G=(V, E) is a graph and p ≥ 2q are positive integers. A (p, q)‐coloring of G is a mapping ϕ: V → {0, 1, …, p‐1} such that for any edge xy of G, q ≤ |ϕ(x)‐ϕ(y)| ≤ p‐q. A color‐list is a mapping L: V → $\cal P$ ({0, 1, …, p‐1}) which assigns to each vertex v a set L(v) of permissible colors. An L‐(p, q)‐coloring of G is a (p, q)‐coloring ϕ of G such that for each vertex v, ϕ(v) ∈ L(v). We say G is L‐(p, q)‐colorable if there exists an L‐(p, q)‐coloring of G. A color‐size‐list is a mapping ℓ which assigns to each vertex v a non‐negative integer ℓ(v). We say G is ℓ‐(p, q)‐colorable if for every color‐list L with |L(v)| = ℓ(v), G is L‐(p, q)‐colorable. In this article, we consider list circular coloring of trees and cycles. For any tree T and for any p ≥ 2q, we present a necessary and sufficient condition for T to be ℓ‐(p, q)‐colorable. For each cycle C and for each positive integer k, we present a condition on ℓ which is sufficient for C to be ℓ‐(2k+1, k)‐colorable, and the condition is sharp. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 249–265, 2007