On Fall Colorings of Graphs

A fall $k$-coloring of a graph $G$ is a proper $k$-coloring of $G$ such that each vertex of $G$ sees all $k$ colors on its closed neighborhood. We denote $\mathrm{F}\mathrm{a}\mathrm{l}\mathrm{l}(G)$ the set of all positive integers $k$ for which $G$ has a fall $k$-coloring. In this paper, we study fall colorings of lexicographic product of graphs and categorical product of graphs and answer a question of \cite{dun} about fall colorings of categorical product of complete graphs. Then, we study fall colorings of union of graphs. Then, we prove that fall $k$-colorings of a graph can be reduced into proper $k$-colorings of graphs in a specified set. Then, we characterize fall colorings of Mycielskian of graphs. Finally, we prove that for each bipartite graph $G$, ${\rm Fall}(G^{c})\subseteq {\chi (G^{c}) }$anditispolynomialtimetodecisionwhetherornot${\rm Fall}(G^{c})={\chi (G^{c}) }$.