| Abstract | : | Let c be a proper k-coloring of a graph G with color classes V1, V2,..., Vk. A vertex v ∈ Vi is called a Grundy vertex if v has a neighbor in each color class Vj for every j < i. The proper k-coloring c is a Grundy k-coloring if every vertex v ∈ Vi is a Grundy vertex for all i, 1 ≤ i ≤ k. The proper k-coloring c of G is a partial Grundy k-coloring if there exists at least one Grundy vertex in each color class Vi, 1 ≤ i ≤ k. The maximum integer k such that there exists a Grundy (or partial Grundy) k-coloring of G is called Grundy number (or partial Grundy number) and it is denoted by Γ(G) (or ∂Γ(G)). I will talk about the results I obtained in my PhD thesis on Grundy coloring and partial Grundy coloring in subclasses of bipartite graphs. It is known that the problems to determine Grundy number or partial Grundy number for bipartite graphs are NP-complete problems. We prove that both the problems remain NP-complete for perfect elimination bipartite graphs. We also give structural characterizations for the Grundy number of some special bipartite permutation graphs, which is a proper subclass of perfect elimination bipartite graphs. We give an upper bound on the partial Grundy number of a general graph, which is better than an existing upper bound. We also prove that the partial Grundy number of chain graphs achieve this new upper bound, where the class of chain graphs is a proper subclass of perfect elimination bipartite graphs. |
