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.
| Identifer | oai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0627104-190111 |
| Date | 27 June 2004 |
| Creators | Yang, Chung-ying |
| Contributors | Xuding Zhu, Sen-Peng Eu, S. C. Liaw, H. G. Yeh |
| Publisher | NSYSU |
| Source Sets | NSYSU Electronic Thesis and Dissertation Archive |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0627104-190111 |
| Rights | unrestricted, Copyright information available at source archive |
Page generated in 0.0092 seconds