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 is an element of {1,. .. , k} are at distance more than i. The packing chromatic number chi rho(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 polynomialtime algorithm that is based on a greedy approach and gives a packing coloring of any graph G. We then define the Grundy packing chromatic number Gamma rho(G) of a graph G as the maximum value that this algorithm yields in G. We present several properties of Gamma rho(G), provide results on the complexity of the problem as well as bounds and some exact results for Gamma rho(G). (c) 2025 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.