期刊論文
| 學年 | 98 |
|---|---|
| 學期 | 1 |
| 出版（發表）日期 | 2010-01-01 |
| 作品名稱 | Multiple Coloring of Cone Graphs |
| 作品名稱（其他語言） | |
| 著者 | Pan, Zhi-Shi; Zhu, Xu-Ding |
| 單位 | 淡江大學數學學系 |
| 出版者 | Philadelphia: Society for Industrial and Applied Mathematics |
| 著錄名稱、卷期、頁數 | SIAM Journal on Discrete Mathematics 24(4), pp.1515-1526 |
| 摘要 | A k-fold coloring of a graph assigns to each vertex a set of k colors, and color sets assigned to adjacent vertices are disjoint. The kth chromatic number Xk(G) of a graph G is the minimum total number of colors needed in a k-fold coloring of G. Given a graph G = (V, E) and an integer m ≥ 0, the m-cone of G, denoted by µm(G), has vertex set (V x {0,1,… , m}) U {u} in which u is adjacent to every vertex of V x {m}, and (x, i)(y, j) is an edge if xy ∈ E and i = j = 0 or xy ∈ E and |i - j| = 1. This paper studies the kth chromatic number of the cone graphs. An upper bound for Xk(µm(G) in terms of Xk(G), k, and m are given. In particular, it is proved that for any graph G, if m ≥ 2k, then Xk(µm(G)) ≤ Xk(G) + 1. We also find a surprising connection between the kth chromatic number of the cone graph of G and the circular chromatic number of G. It is proved that if Xk(G)/k > Xc((G) and Xk(G) is even, then for sufficiently large m, Xk(µm(G)) = Xk(G). In particular, if X(G) > Xc(G) and X(G) is even, then for sufficiently large m, X(µm(G)) = X(G). |
| 關鍵字 | Multiple coloring; Cone graphs; Mycielski graphs; Fractional chromatic number; Kneser graphs |
| 語言 | en |
| ISSN | 0895-4801 1095-7146 |
| 期刊性質 | 國外 |
| 收錄於 | SCI |
| 產學合作 | |
| 通訊作者 | Pan, Zhi-Shi; Zhu, Xu-Ding |
| 審稿制度 | |
| 國別 | USA |
| 公開徵稿 | |
| 出版型式 | 紙本 |
| 相關連結 |
機構典藏連結 ( http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/56752 ) |