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.
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. Erd\H{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
Zhou, H. , Shiu, W. C. and Lam, P. Che Bor (2012). The $L(2,1)$-choosability of cycle. Transactions on Combinatorics, 1(3), 21-38. doi: 10.22108/toc.2012.1895
MLA
Zhou, H. , , Shiu, W. C. , and Lam, P. Che Bor. "The $L(2,1)$-choosability of cycle", Transactions on Combinatorics, 1, 3, 2012, 21-38. doi: 10.22108/toc.2012.1895
HARVARD
Zhou, H., Shiu, W. C., Lam, P. Che Bor (2012). 'The $L(2,1)$-choosability of cycle', Transactions on Combinatorics, 1(3), pp. 21-38. doi: 10.22108/toc.2012.1895
CHICAGO
H. Zhou , W. C. Shiu and P. Che Bor Lam, "The $L(2,1)$-choosability of cycle," Transactions on Combinatorics, 1 3 (2012): 21-38, doi: 10.22108/toc.2012.1895
VANCOUVER
Zhou, H., Shiu, W. C., Lam, P. Che Bor The $L(2,1)$-choosability of cycle. Transactions on Combinatorics, 2012; 1(3): 21-38. doi: 10.22108/toc.2012.1895