科研之友
微信
新浪微博
Facebook
分享链接
摘要
A k-fold coloring of a graph is a function that assigns to each vertex a set of k colors, so that the color sets assigned to adjacent vertices are disjoint. The kth chromatic number of a graph G, denoted by chi(k)(G), is the minimum total number of colors used in a k-fold coloring of G. Let mu(G) denote the Mycielskian of G. For any positive integer k, it holds that chi(k)(G) 1 <= chi(k)(mu(G))<=chi(k)(G) k (W. Lin, Disc. Math., 308 (2008), 3565-3573). Although both bounds are attainable, it was proved in (Z. Pan, X. Zhu, Multiple coloring of cone graphs, manuscript, 2006) that if k >= 2 and chi(k)(G)<= 3k-2, then the upper bound can be reduced by 1, i.e., chi k(mu(G))<=chi(k)(G) k-1. We conjecture that for any n >= 3k-1, there is a graph G with chi(k)(G)= n and chi(k)(mu(G))= n k. This is equivalent to conjecturing that the equality chi(k)(mu(K(n,k)))=n k holds for Kneser graphs K(n,k) with n >= 3k-1. We confirm this conjecture for k=2, 3, or when n is a multiple of k or n >= 3k(2)/In k. Moreover, we determine the values of chi k(mu(C(2q 1))) for 1 <= k <= q.
