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

Zhou, Haiying; Shiu, Wai Chee; Lam, Peter Che Bor

doi:10.22108/toc.2012.1895

تعداد نشریات	43
تعداد شماره‌ها	1,637
تعداد مقالات	13,304
تعداد مشاهده مقاله	29,860,362
تعداد دریافت فایل اصل مقاله	11,940,942

	The $L(2,1)$-choosability‎ ‎of cycle
Transactions on Combinatorics
مقاله 4، دوره 1، شماره 3، آذر 2012، صفحه 21-38 اصل مقاله (521.55 K)
نوع مقاله: Research Paper
شناسه دیجیتال (DOI): 10.22108/toc.2012.1895
نویسندگان
Haiying Zhou¹؛ Wai Chee Shiu^* ¹؛ Peter Che Bor Lam²
¹Hong Kong Baptist University
²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‎.
کلیدواژه‌ها
L(2, 1)-labeling؛ Choosability؛ cycle؛ Path

مراجع
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
آمار تعداد مشاهده مقاله: 4,425 تعداد دریافت فایل اصل مقاله: 2,903

سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب

پیوندهای مفید

اخبار و اعلانات

آمار

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