More Bounds For The Grundy Number Of Graphs

A coloring of a graph G=(V,E) is a partition{V1,V2,…,Vk} of V into independent sets or color classes. A vertex υ∈Vi is a Grundy vertex if it is adjacent to at least one vertex in each color class Vj for every j<i. A coloring is a Grundy coloring if every vertex is a Grundy vertex,and the Grundy number Γ(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{P4,C4}-free graph by supporting a conjecture of Zaker, which says that T(G)≥δ(G)+1 for any C4-free graph G.