| 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 |
| 公開徵稿 | |
| 出版型式 | 電子版 |
| 相關連結 |
機構典藏連結 ( http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/56754 ) |
GoogleAnalytics