Multiple Coloring of Cone Graphs

doi:10.1137/070691486

淡江大學機構典藏 > 理學院 > 應用數學與數據科學學系 > 期刊論文 > Item 987654321/56752

請使用永久網址來引用或連結此文件: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/56752

題名:	Multiple Coloring of Cone Graphs
作者:	Pan, Zhishi;Zhu, Xuding
貢獻者:	淡江大學數學學系
關鍵詞:	Multiple coloring;Cone graphs;Mycielski graphs;Fractional chromatic number;Kneser graphs
日期:	2010
上傳時間:	2011-09-07 11:54:53 (UTC+8)
出版者:	Philadelphia: Society for Industrial and Applied Mathematics
摘要:	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).
關聯:	SIAM Journal on Discrete Mathematics 24(4), pp.1515-1526
DOI:	10.1137/070691486
顯示於類別:	[應用數學與數據科學學系] 期刊論文

文件中的檔案:

檔案	大小	格式	瀏覽次數
0895-4801_24(4)p1515-1526.pdf	241Kb	Adobe PDF	294	檢視/開啟
index.html	0Kb	HTML	256	檢視/開啟
index.html	0Kb	HTML	248	檢視/開啟

在機構典藏中所有的資料項目都受到原著作權保護.

TAIR相關文章

資料載入中.....