Bounds for the Grundy chromatic number of graphs in terms of domination number (Q6073792)

For a graph \(G=(V,E)\), a Grundy \(k\)-coloring of a graph \(G\) is a proper coloring of \(V(G)\) with colors \(\{1, 2, \dots, k\}\) such that for each color \(j\), any vertex colored \(j\) is adjacent to a vertex colored \(i\) for every \(i<j\). The Grundy chromatic number of \(G\) is the largest integer \(k\) such that there exists a Grundy \(k\)-coloring for \(G\). For a given ordering of \(V(G)\), the greedy coloring algorithm assigns the smallest available color to every vertex with respect to the ordering. It is known that the Grundy chromatic number of \(G\) equals the largest number of colors used by the greedy coloring algorithm of any ordering of \(V(G)\). A star partition of \(G\) is a partition of \(V(G)\) into subsets \(V_1, V_2,\dots, V_k\) such that for any \(i\) the subgraph of \(G\) induced by \(V_i\) contains a vertex adjacent to all other vertices of \(V_i\). A subset \(D \subseteq V(G)\) is a dominating set of \(G\) if any vertex in \(V(G) \setminus D\) is adjacent to a vertex of \(D\). The domination number of \(G\) is the smallest cardinality of any dominating set in \(G\). It is known that for a graph without isolated vertices \(G\), the smallest number of subsets of a star partition of \(G\) equals the domination number of \(G\). The paper investigates the Grundy chromatic number using the star partition of graphs. In particular, it provides upper bounds for the Grundy chromatic number that depend on the order, domination number, and length of the shortest cycle of general and triangle-free graphs.