Multicoloring and Mycielski construction

作者：Lin Wensong^*

来源：Discrete Mathematics, 2008, 308(16): 3565-3573.

DOI：10.1016/j.disc.2007.07.015

• k-tuple coloring
• a/b-coloring
• fractional chromatic number
• homomorphism
• Mycielskian
• p-Mycielskian
• Kneser graph

The generalized Mycielskians of graphs (also known as cones over graphs) are the natural generalization of the Mycielskians of graphs (which were first introduced by Mycielski in 1955). Given a graph G and any integer p >= 0, one can transform G into a new graph mu(p)(G), the p-Mycielskian of G. In this paper, we study the kth chromatic numbers chi k of Mycielskians and generalized Mycielskians of graphs. We show that chi k (G) + 1 <= chi k(mu(G)) <= chi k(G) + k, where both upper and lower bounds are attainable. We then investigate the kth chromatic number of Mycielskians of cycles and determine the kth chromatic number of p-Mycielskian of a complete graph K-n for any integers k >= 1, p >= 0 and n >= 2. Finally, we prove that if a graph G is a/b-colorable then the p-Mycielskian of G, mu(p)(G), is (at + b(p+1))/bt-colorable, where t = Sigma(p)(i=0)(a-b)(i) b(p-i). And thus obtain graphs G with m(G) grows exponentially with the order of G, where m(G) is the minimal denominator of a a/b-coloring of G with chi(f)(G) = a/b.

• 出版日期2008-8-28
• 单位东南大学