The $L(2,1)$-choosability‎ ‎of cycle

Document Type: Research Paper

Authors

1 Hong Kong Baptist University

2 United International College

Abstract

‎For a given graph $G=(V,E)$‎, ‎let $\mathscr L(G)=\{L(v)‎ : ‎v\in V\}$ be a prescribed list assignment‎. ‎$G$ is $\mathscr L$-$L(2,1)$-colorable if there exists a vertex labeling $f$ of $G$ such that $f(v)\in L(v)$ for all $v \in V$; $|f(u)-f(v)|\geq 2$ if $d_G(u,v) = 1$; and $|f(u)-f(v)| \geq 1$ if $d_G(u,v)=2$‎. ‎If $G$ is $\mathscr L$-$L(2,1)$-colorable for every list assignment $\mathscr L$ with $|L(v)|\geq k$ for all $v\in V$‎, ‎then $G$ is said to be $k$-$L(2,1)$-choosable‎. ‎In this paper‎, ‎we prove all cycles are $5$-$L(2,1)$-choosable‎.

Keywords

Main Subjects


J. R. Griggs and R. K. Yeh (1992). Labeling graphs with a condition at distance two. SIAM J. Discrete Math.. 5, 586-595
G. J. Chang and D. Kuo (1996). The $L(2,1)$-labeling problem on graphs. SIAM J. Discrete Math.. 9, 309-316
G. J. Chang, W. T. Ke, D. Kuo, D. F. Liu and R. K. Yeh (2000). On $L(d,1)$-labelings of graphs. Discrete Math.. 220, 57-66
F. S. Roberts (1988). Private communication with J. R. Griggs.
W. K. Hale (1980). Frequency assignment: theory and applications. Proc. IEEE. 68, 1497-1514
V. G. Vizing (1976). Vertex coloring with given colors (in Russian). Diskret. Analiz. 29, 3-10
P. ErdH{o}s, A. L. Rubin and H. Taylor (1979). Choosability in graphs. Congres. Numer.. 26, 125-157
C. Thomassen (1994). Every planar graph is 5-choosable. Journal of Combinatorial Theory, Ser. B. 62, 180-181
C. Thomassen (1995). 3-list-coloring planar graphs of girth 5. Journal of Combinatorial Theory, Ser. B. 64, 101-107
P. C. B. Lam, B. G. Xu and J. Z. Liu (1999). The 4-choosability of plane graphs without 4-cycles. J. of Combin. Theory, Ser. B. 76, 117-126
P. C. B. Lam, W. C. Shiu and B. G. Xu (2001). On structure of some plane graphs with applications to choosability. J. of Combin. Theory, Ser. B. 82, 285-296
P. C. B. Lam, W. C. Shiu and Z. M. Song (2005). The 3-choosability of plane graphs of girth 4. Discrete Math.. 294, 297-301
Y-J. Chen (2004). The list-$L(2,1)$-labeling problem of graphs. M. Phil. Thesis, Dept. of Applied Math., National Dong Hwa University, Taiwan.
M. Voigt and B. Wirth (1997). On 3-colorable non-4-choosable planar graphs. J. Graph Theory. 24 (3), 233-235
M. Voigt (1995). A not 3-choosable planar graph without 3-cycles. Discrete Math.. 146, 325-328