Dunbar, J. E.; Hedetniemi, S. M.; Hedetniemi, S. T.; Jacobs, D. P.; Knisely, J.; Laskar, R. C.; Rall, D. F. Fall colorings of graphs. (English) Zbl 0962.05020 J. Comb. Math. Comb. Comput. 33, 257-273 (2000). Authors’ 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,\dots, V_k\}\) of the vertices of \(G\) into independent sets \(V_i\), or color classes. A vertex \(v\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 by \(\chi_f(G)\) (\(\psi_f(G)\)) to equal the minimum (maximum) order of a fall coloring of \(G\), respectively. In this paper we relate full colorings to other colorings of graphs and to independent dominating sets in graphs.”In particular, inequalities are established between \(\chi_f(G)\), \(\psi_f(G)\) and other chromatic and achromatic numbers, and it is shown that \(\psi_f(G)\) is equal to the maximum number of independent dominating sets into which the vertex-set of \(G\) can be partitioned. Other results include the conditions under which the Cartesian products of paths and cycles have a fall \(k\)-colouring and a proof that it is NP-complete to decide if a given graph has a fall colouring. Reviewer: Timothy R.Walsh (Montreal) Cited in 6 ReviewsCited in 14 Documents MSC: 05C15 Coloring of graphs and hypergraphs Keywords:idomatic number; Grundy number; colorings; chromatic number; achromatic number; independent dominating sets PDFBibTeX XMLCite \textit{J. E. Dunbar} et al., J. Comb. Math. Comb. Comput. 33, 257--273 (2000; Zbl 0962.05020)