List circular coloring of trees and cycles

✍ Scribed by André Raspaud; Xuding Zhu

• Publisher: John Wiley and Sons
• Year: 2007
• Tongue: English
• Weight: 255 KB
• Volume: 55
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20234

✦ Synopsis

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