On the packing chromatic number of Moore graphs

Abstract

The \emph{packing chromatic number ${\chi }_{\rho }(G)$} of a graph $G$ is the smallest integer $k$ for which there exists a vertex coloring $\Gamma :V(G)\to \{1,2,\dots ,k\}$ such that any two vertices of color $i$ are at distance at least $i+1$. For $g\in \{6,8,12\}$, $(q+1,g)$-Moore graphs are $(q+1)$-regular graphs with girth $g$ which are the incidence graphs of a symmetric generalized $g/2$-gons of order $q$. In this paper we study the packing chromatic number of a $(q+1,g)$-Moore graph $G$. For $g=6$ we present the exact value of ${\chi }_{\rho }(G)$. For $g=8$, we determine ${\chi }_{\rho }(G)$ in terms of the intersection of certain structures in generalized quadrangles. For $g=12$, we present lower and upper bounds for this invariant when $q\ge 9$ an odd prime power.

14 pages, 2 figures