A note on the packing chromatic number of lexicographic products

Abstract

The packing chromatic number ${\chi }_{\rho }(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\circ H$ of graphs $G$ and $H$. Both bounds coincide in many cases. In particular this happens if $|V(H)|-\alpha (H)\ge \mathrm{diam}(G)-1$, where $\alpha (G)$ denotes the independence number of $G$.

6 pages, 1 figure, 9 refwerences