On partial Grundy coloring of bipartite graphs and chordal graphs

A proper k-coloring with colors 1, 2,..., k of a graph G = (V, E) is an ordered partition (V-1, V-2,, V-k) of V such that V, is an independent set or color class in which each vertex v is an element of V-i is assigned color i for 1 <= i <= k. A vertex v is an element of V-i is a Grundy vertex if it is adjacent to at least one vertex in each color class V-j, for every j, j < i. A proper coloring is a partial Grundy coloring if every color class has at least one Grundy vertex in it and the partial Grundy number, denoted as partial derivative Gamma(G), is the maximum number of colors used in a partial Grundy coloring. Given a graph G and an integer k, 1 <= k <= n, the PARTIAL GRUNDY NUMBER DECISION PROBLEM iS LO decide whether partial derivative Gamma(G) >= k. We prove a new upper bound for the partial Grundy number of a graph and show that this upper bound is sharper than the existing upper bound in the literature. It is known that PARTIAL GRUNDY NUMBER DECISION PROBLEM IS NP-complete for the class of bipartite graphs. We strengthen this result by showing that the problem remains NP-complete even for perfect elimination bipartite graphs and star-convex bipartite graphs, two proper subclasses of the class of bipartite graphs. On the positive side, we give a linear time algorithm to determine the partial Grundy number of a chain graph. It is also known that PARTIAL GRUNDY NUMBER DECISION PROBLEM IS NP-complete for the class of chordal graphs. We strengthen this result by showing that the problem remains NP-complete even for doubly chordal graphs, a proper subclass of the class of chordal graphs. On the positive side, we give linear time algorithms to determine the partial Grundy number of split graphs and block graphs, two important subclasses of the class of chordal graphs. (C) 2019 Elsevier B.V. All rights reserved.