On Fall Colorings of Graphs

Abstract

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 $\text{Fall}(G)$ the set of all positive integers $k$ for which $G$ has a fall $k$-coloring. In this paper, we study fall colorings of the lexicographic product of graphs and the categorical product of graphs. Additionally, we show that for each graph $G$, $\text{Fall}(M(G))=\mathrm{\varnothing }$, where $M(G)$ is the Mycielskian of the graph $G$. Finally, we prove that for each bipartite graph $G$, $\text{Fall}(G^c)\subseteq \{\chi (G^c)\}$ and it is polynomial time to decide whether $\text{Fall}(G^c)=\{\chi (G^c)\}$ or not.