Circular consecutive choosability of k-choosable graphs

淡江大學機構典藏 > 理學院 > 數學學系暨研究所 > 期刊論文 > Item 987654321/56754

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/56754

题名:	Circular consecutive choosability of k-choosable graphs
作者:	Liu, Daphne;Serguei Norine;Pan, Zhishi;Zhu, Xuding
贡献者:	淡江大學數學學系
关键词:	Choosability;Circular consecutive choosability
日期:	2011-07
上传时间:	2011-09-07 12:01:02 (UTC+8)
出版者:	Hoboken: John Wiley & Sons, Inc.
摘要:	Let S(r) denote a circle of circumference r. The circular consecutive choosability chcc(G) of a graph G is the least real number t such that for any r≥χc(G), if each vertex v is assigned a closed interval L(v) of length t on S(r), then there is a circular r-coloring f of G such that f(v)∈L(v). We investigate, for a graph, the relations between its circular consecutive choosability and choosability. It is proved that for any positive integer k, if a graph G is k-choosable, then chcc(G)≦k + 1 − 1/k; moreover, the bound is sharp for k≥3. For k = 2, it is proved that if G is 2-choosable then chcc(G)≦2, while the equality holds if and only if G contains a cycle. In addition, we prove that there exist circular consecutive 2-choosable graphs which are not 2-choosable. In particular, it is shown that chcc(G) = 2 holds for all cycles and for K2, n with n≥2. On the other hand, we prove that chcc(G)＞2 holds for many generalized theta graphs.
關聯:	Journal of Graph Theory 67(3), pp.178-197
DOI:	10.1002/jgt.20524
显示于类别:	[數學學系暨研究所] 期刊論文

文件中的档案:

档案	大小	格式	浏览次数
	0Kb	HTML	308	检视/开启
11 Circular Consecutive Choosability of k-Choosable Graphs.pdf	190Kb	Adobe PDF	582	检视/开启
Circular consecutive choosability of k-choosable graphs.pdf	190Kb	Adobe PDF	1	检视/开启
index.html	0Kb	HTML	187	检视/开启

在機構典藏中所有的数据项都受到原著作权保护.

TAIR相关文章