科研之友
微信
新浪微博
Facebook
分享链接
摘要
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 chi(k)(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 mu(m)(G), has vertex set (V x {0, 1,..., m})boolean OR{u} in which u is adjacent to every vertex of V x{m}, and (x, i)(y, j) is an edge if xy is an element of E and i = j = 0 or xy is an element of E and vertical bar i-j vertical bar = 1. This paper studies the kth chromatic number of the cone graphs. An upper bound for chi(k)(mu(m)(G)) in terms of chi(k)(G), k, and m are given. In particular, it is proved that for any graph G, if m >= 2k, then chi(k)(mu(m)(G)) <= chi(k)(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 chi(k)(G)/k > chi(c)(G) and chi(k)(G) is even, then for sufficiently large m, chi(k)(mu(m)(G)) = chi(k)(G).
