# List circular coloring of even cycles

Abstract (Summary)

Suppose G is a graph and p >= 2q are positive integers. A
color-list is a mapping L: V --> P(0, 1,...,p-1) which assigns to each vertex a set L(v) of
permissible colors. An L-(p, q)-coloring of G is a (p,
q)-coloring h of G such that for each vertex v,
h(v) in L(v). We say G is L-(p, q)-colorable if
such a coloring exists. A color-size-list is a mapping f: V -->{0, 1, 2,..., p}, which assigns to each vertex v a
non-negative integer f(v). We say G is f-(p, q)-colorable
if for every color-list L with |{L}(v)| = f(v), G is
L-(p, q)-colorable. For odd cycles C, Raspaud and Zhu
gave a sharp sufficient condition for a color-size-list f under
which C is f-(2k+1, k)-colorable. The corresponding
question for even cycles remained open. In this paper, we
consider list circular coloring of even cycles. For each even cycle C of length n and for each positive integer k, we
give a condition on f which is sufficient and sharp for C to
be f-(2k+1, k)-colorable.
Bibliographical Information:

Advisor:Xuding Zhu; Sen-Peng Eu; S. C. Liaw; H. G. Yeh

School:National Sun Yat-Sen University

School Location:China - Taiwan

Source Type:Master's Thesis

Keywords:even cycle circular coloring

ISBN:

Date of Publication:06/27/2004