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)) = \emptyset\), 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.