Some comparative results concerning the Grundy and \(b\)-chromatic number of graphs (Q2243130)

A \(b\)-coloring is a proper vertex coloring of a graph \(G\) such that each color class \(C_i\), i.e., a subset of vertices of \(G\) assigned to color \(i\), contains a vertex that has a neighbor in all other color classes. The \(b\)-chromatic number of a graph \(G\) is the largest integer \(\chi_b(G)\) for which \(G\) admits a \(b\)-coloring with \(\chi_b(G)\) colors. A Grundy coloring of a graph \(G\) is a proper vertex coloring of \(G\), such that for every two color classes \(C_i\) and \(C_j\), \(i < j\), each vertex in \(C_j\) has an adjacent vertex in \(C_i\). The largest integer \(k\) that allows a Grundy coloring of \(G\) with \(k\) colors is called the Grundy number of \(G\) and denoted by \(\Gamma(G)\). It is known that the Grundy number of \(G\) is equivalent to the largest number of colors used by the greedy coloring procedure in \(G\). This note considers relations between the \(b\)-chromatic number and the Grundy number of a graph. In particular, it is shown that the \(b\)-chromatic number of \(G\) is bounded below by \(\Gamma(G) - \lceil \log \Gamma(G) \rceil \) if the maximum degree of \(G\) does not exceed \(2^{\frac{g-4}{2}}-1\), where \(g\) denotes the girth of \(G\). In addition, if a \(K_{2,3}\)-free graph \(G\) satisfies the condition that for each induced subgraph \(H\) of \(G\) we have \(\chi_b(H) \le \chi_b(G)\), then it is established that the lower bound for the \(b\)-chromatic number of \(G\) is \(\lfloor ^3\!\!\!\!\sqrt{2\Gamma(G)} \rfloor \).