Color chain of a graph (Q659728): Difference between revisions

The chromatic number of a graph \(G\) is written \(\chi(G)\). A proper \(k\)-coloring of a graph \(G\) with color classes \(V_1, \dots, V_k\) is a {\parindent=6mm \begin{itemize}\item[-] \(k\)-fall coloring if each vertex in \(V_i\) is adjacent to at least one vertex in \(V_j\), \(j\not= i\); the last, respectively, largest positive integer \(k\) for which \(G\) has a \(k\)-fall coloring is denoted by \(\chi_f(G)\), respectively, \(\Psi_f(G)\); \item[-] \(b\)-coloring if each \(V_i\) has a vertex adjacent to at least one vertex in \(V_j\), \(j\not= i\); the largest positive integer \(k\) for which \(G\) has a \(b\)-coloring using \(k\) colors is denoted by \(\phi(G)\); \item[-] partial Grundy coloring if, for each \(2\leq i\leq k\), there exists a vertex in \(V_i\) that is adjacent to at least one vertex in each \(V_j\), \(j < i\); the largest positive integer \(k\) for which \(G\) has a partial Grundy coloring with \(k\) colors is denoted by \(\partial\Gamma(G)\); \item[-] complete coloring if the union of two color classes is not an independent set of \(G\); the largest positive integer \(k\) for which \(G\) has a complete coloring with \(k\) colors is denoted by \(\Psi(G)\). \end{itemize}} It is clear that for any graph \(G\) admitting a fall coloring, \(\chi(G)\leq \chi_f(G)\leq \Psi_f(G)\leq \phi(G)\leq \partial\Gamma(G)\leq \Psi(G)\). The authors exhibit an infinite family of graphs \(G\) with a strictly increasing color chain: \(\chi(G)< \chi_f(G)< \Psi_f(G)< \phi(G)< \partial\Gamma(G)< \Psi(G)\). The existence of such a chain was raised in [\textit{J.E. Dunbar}, \textit{S.M. Hedetniemi}, \textit{S.T. Hedetniemi}, \textit{D.P. Jacobs}, \textit{J. Kniseley}, \textit{R.C. Laskar}, and \textit{D.F. Rall}, ``Fall coloring of graphs,'' J. Comb. Math. Comb. Comput. 33, 257--273 (2000); Zbl 0962.05020)]