Color chain of a graph
type: Item
instance of: scholarly article
title: Color chain of a graph
zbMATH Open document ID: 1244.05086
author: R. Balakrishnan
author: T. Kavaskar
published in: Graphs and Combinatorics
publication date: 2012-01-24T00:00:00Z
review text: 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)]
reviewed by: Van Bang Le
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 5999858
zbMATH Keywords: chromatic number
zbMATH Keywords: Fall chromatic number
zbMATH Keywords: Fall achromatic number
zbMATH Keywords: \(b\)-Chromatic number
zbMATH Keywords: Partial Grundy number and achromatic number
MaRDI profile type: Publication
full work available at URL: s00373-010-0989-7
OpenAlex ID: W2125677183
cites work: Fall coloring of graphs I
cites work: Q4504904
cites work: On the equality of the partial Grundy and upper ochromatic numbers of graphs
cites work: The achromatic number of a graph
cites work: The b-chromatic number of a graph
cites work: Fall colouring of bipartite graphs and Cartesian products of graphs
cites work: An algorithm for partial Grundy number on trees
DOI: 10.1007/S00373-010-0989-7
Recommended article: Q4558664
Recommended article: Q4635974
Recommended article: Q3708830
Recommended article: Coloring chains
Recommended article: Rainbow colourings of chains
Recommended article: Color-Induced Graph Colorings
Recommended article: Q5855395
Recommended article: Q4559905
Recommended article: Q5119831
Recommended article: The color space of a graph
description: scientific article; zbMATH DE number 5999858