More bounds for the Grundy number of graphs

Abstract

A coloring of a graph $G=(V,E)$ is a partition $\{V_1,V_2,\dots ,V_k\}$ of $V$ into independent sets or color classes. A vertex $v\in V_i$ is a Grundy vertex if it is adjacent to at least one vertex in each color class $V_j$ for every $j<i$. A coloring is a Grundy coloring if every vertex is a Grundy vertex, and the Grundy number $\hat{I}“(G)$ of a graph $G$ is the maximum number of colors in a Grundy coloring. We provide two new upper bounds on Grundy number of a graph and a stronger version of the well-known Nordhaus-Gaddum theorem. In addition, we give a new characterization for a $\{P_4,C_4\}$-free graph by supporting a conjecture of Zaker, which says that $\hat{I}“(G)\ge \hat{I}´(G)+1$ for any $C_4$-free graph $G$.

12 pages, 1 figure, accepted for publication in Journal of Combinatorial Optimization