Grundy Packing Coloring of Graphs

A map c:V(G)→\1,,k\ of a graph G is a packing k-coloring if every two different vertices of the same color i∈ \1,,k\ are at distance more than i. The packing chromatic number χρ(G) of G is the smallest integer k such that there exists a packing k-coloring. In this paper we introduce the notion of Grundy packing chromatic number, analogous to the Grundy chromatic number of a graph. We first present a polynomial-time algorithm that is based on a greedy approach and gives a packing coloring of G. We then define the Grundy packing chromatic number Γρ(G) of a graph G as the maximum value that this algorithm yields in a graph G. We present several properties of Γρ(G), provide results on the complexity of the problem as well as bounds and some exact results for Γρ(G).