Menu
A fall coloring of a graph \( G \) is a color partition of the vertex set of \( G \) in such a way that every vertex of \( G \) is a colorful vertex in \( G \) (that is, it has at least one neighbor in each of the other color classes). The fall coloring number \( \chi_f(G) \) of \( G \) is the minimum size of a fall color partition of \( G \) (when it exists). In this paper, we show that the Mycielskian \( \mu(G) \) of any graph \( G \) does not have a fall coloring and that the generalized Mycielskian \( \mu_m(G) \) of a graph \( G \) may or may not have a fall coloring. More specifically, we show that if \( G \) has a fall coloring, then \( \mu_{3m}(G) \) has also a fall coloring for \( m \geq 1 \), and that \( \chi_f(\mu_{3m}(G)) \leq \chi_f(G) + 1 \).