Multi-coloring the Mycielskian of graphs

✍ Scribed by Wensong Lin; Daphne Der-Fen Liu; Xuding Zhu

• Publisher: John Wiley and Sons
• Year: 2009
• Tongue: English
• Weight: 129 KB
• Volume: 63
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20429

✦ Synopsis

Abstract

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 k__th chromatic number of a graph G, denoted by χ~k~(G), is the minimum total number of colors used in a k‐fold coloring of G. Let µ(G) denote the Mycielskian of G. For any positive integer k, it holds that χ~k~(G) + 1≤χ~k~(µ(G))≤χ~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 χ~k~(G)≤3__k−2, then the upper bound can be reduced by 1, i.e., χ~k~(µ(G))≤χ~k~(G) + k−1. We conjecture that for any n≥3__k__−1, there is a graph G with χ~k~(G)=n and χ~k~(µ(G))=n+ k. This is equivalent to conjecturing that the equality χ~k~(µ(K(n, k)))=n+k holds for Kneser graphs K(n, k) with n≥3__k__−1. We confirm this conjecture for k=2, 3, or when n is a multiple of k or n≥3__k__^2^/ln k. Moreover, we determine the values of χ~k~(µ(C~2__q__+1~)) for 1≤k≤q. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 311–323, 2010