Fall Colorings of Graphs

We introduce a new class of colorings of graphs and define and study two new graph coloring parameters. A \emph{coloring} of a graph \(G = (V,E)\) is a partition \(\Pi = \{V_1, V_2, \ldots, V_k\}\) of the vertices of \(G\) into independent sets \(V_i\), or \emph{color classes}. A vertex \(v_i \in V_i\) is called \emph{colorful} if it is adjacent to at least one vertex in every color class \(V_j\), \(i \neq j\). A \emph{fall coloring} is a coloring in which every vertex is colorful. If a graph \(G\) has a fall coloring, we define the \emph{fall chromatic number} (\emph{fall achromatic number}) of \(G\), denoted \(\chi_f(G)\), (\(\psi_f(G)\)) to equal the minimum (maximum) order of a fall coloring of \(G\), respectively. In this paper, we relate fall colorings to other colorings of graphs and to independent dominating sets in graphs.