×

Fall colorings of graphs. (English) Zbl 0962.05020

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.

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite