List circular coloring of even cycles

by Yang, Chung-ying

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.