A characterization of 4-χ ρ -(vertex-)critical graphs


Jasmina Ferme




Given a graph G, a function c : V(G) −→ {1, . . . , k} with the property that for every u , v, c(u) = c(v) = i implies that the distance between u and v is greater than i, is called a k-packing coloring of G. The smallest integer k for which there exists a k-packing coloring of G is called the packing chromatic number of G, and is denoted by χρ(G). Packing chromatic vertex-critical graphs are the graphs G for which χρ(G − x) < χρ(G) holds for every vertex x of G. A graph G is called a packing chromatic critical graph if for every proper subgraph H of G, χρ(H) < χρ(G). Both of the mentioned variations of critical graphs with respect to the packing chromatic number have already been studied [6, 23]. All packing chromatic (vertex-)critical graphs G with χρ(G) = 3 were characterized, while there were known only partial results for graphs G with χρ(G) = 4. In this paper, we provide characterizations of all packing chromatic vertex-critical graphs G with χρ(G) = 4 and all packing chromatic critical graphs G with χρ(G) = 4.