¡@

Chi_c of Mycielski graphs

¡@

Given a graph G=(V, E), the Mycielskian of G, denoted by M(G) has vertex set V \cup V' \cup {u}, where V' = {x': x \in V}.  The edge set of M(G) is E' = E \cup {x'y: xy \in E} \cup {ux': x' \in V'}.  Let M^1(G) = M(G) and M^t(G) = M(M^{t-1}(G))  for t >= 2. 

Conjecture: If t <= n-2, then chi_c(M^t(K_n)) = \chi(M^t(K_n)) = n + t

The conjecture is true for t=1, 2, and remains open for t >= 3 [CHZ]. It is also known that [Liu02] that if n >=2^{t-1}+2t-2, then chi_c(M^t(K_n)) = \chi(M^t(K_n)) = n + t. This improves a similar result in [HZ].

Gabor Simoyi and Gabor Tardos [ST] proved that whenever n+t is even, chi_c(M^t(K_n)) = \chi(M^t(K_n)) = n + t. Their result refers generalized Mycielskian of G, and is stronger than the result stated above. 

Reference 

[Liu02] D. Liu, Circular Chromatic Number for Iterated Mycielski Graphs. Preprint  2002.