2015/07/04 by Zixing Tang, Baoyindureng Wu, Tang, Zixing +5 · 1 citation
Computer Science · Mathematics · #05C15 #05C17 #05C69 #05C75 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications #math.CO #msc:05C15 #msc:05C17 #msc:05C69 #msc:05C75
paper · pdf · doi:10.48550/arxiv.1507.01080
12 pages, 1 figure, accepted for publication in Journal of Combinatorial Optimization
openalex publication_date 2015/07/04 · arxiv created 2015/12/08 · arxiv updated 2015/12/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A coloring of a graph G=(V,E) is a partition \V1, V2, …, Vk\ of V into independent sets or color classes. A vertex v∈ 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 Γ(G)≥ δ(G)+1 for any C4-free graph G.