Type: Article
Publication Date: 2007-02-22
Citations: 7
DOI: https://doi.org/10.1002/jgt.20234
Abstract Suppose G =( V , E ) is a graph and p ≥ 2 q 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 ≥ 2 q , 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 ℓ‐(2 k +1, k )‐colorable, and the condition is sharp. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 249–265, 2007