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

Document Type : Research Paper


1 Hong Kong Baptist University

2 United International College


‎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‎.


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. 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
Volume 1, Issue 3 - Serial Number 3
September 2012
Pages 21-38
  • Receive Date: 27 July 2012
  • Revise Date: 11 October 2012
  • Accept Date: 11 October 2012
  • Published Online: 01 September 2012