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).