Circular consecutive choosability of k-choosable graphs
學年 99
學期 2
出版(發表)日期 2011-07-01
作品名稱 Circular consecutive choosability of k-choosable graphs
著者 Liu, Daphne; Serguei Norine; Pan, Zhi-Shi; Zhu, Xu-Ding
單位 淡江大學數學學系
出版者 Hoboken: John Wiley & Sons, Inc.
著錄名稱、卷期、頁數 Journal of Graph Theory 67(3), pp.178-197
摘要 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.
關鍵字 Choosability; Circular consecutive choosability
語言 en
ISSN 1097-0118
期刊性質 國外
收錄於 SCI
國別 USA
出版型式 電子版

機構典藏連結 ( )