Fall Colorings of Graphs

J. E. Dunbar1, S. M. Hedetniemi2, S. T. Hedetniemi2, D. P. Jacobs 2, J. Knisely3, R. C. Laskar4, D. F. Rall5
1Dept. Mathematics, Converse College, Spartanburg, SC 29302-0006
2Dept. Computer Science, Clemson University, Clemson, SC 29634-1906
3Dept. Mathematics, Bob Jones University, Greenville, SC 29614
4Dept. Mathematical Sciences, Clemson University, Clemson, SC 29634-1906
5Dept. Mathematics, Furman University, Greenville, SC 29613

Abstract

We introduce a new class of colorings of graphs and define and study two new graph coloring parameters. A \({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 \({color\; classes}\). A vertex \(v_i \in V_i\) is called \({colorful}\) if it is adjacent to at least one vertex in every color class \(V_j\), \(i \neq j\). A \({fall \;coloring}\) is a coloring in which every vertex is colorful. If a graph \(G\) has a fall coloring, we define the \({fall\; chromatic\; number}\) (\({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.