2019/09/25 by Božović, Dragana, Peterin, Iztok
#05C12 #05C15 #05C70 #05C76 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1909.11325
The packing chromatic number χρ(G) of a graph G is the smallest integer k such that there exists a k-vertex coloring of G in which any two vertices receiving color i are at distance at least i+1. In this short note we present upper and lower bound for the packing chromatic number of the lexicographic product G∘ H of graphs G and H. Both bounds coincide in many cases. In particular this happens if |V(H)|-α(H)≥ \rm diam(G)-1, where α(G) denotes the independence number of G.