On Packing Colorings of Distance Graphs

Abstract

The {\em packing chromatic number} ${\chi }_{\rho }(G)$ of a graph $G$ is the least integer $k$ for which there exists a mapping $f$ from $V(G)$ to $\{1,2,\dots ,k\}$ such that any two vertices of color $i$ are at distance at least $i+1$. This paper studies the packing chromatic number of infinite distance graphs $G(\mathbb{Z},D)$, i.e. graphs with the set $\mathbb{Z}$ of integers as vertex set, with two distinct vertices $i,j\in \mathbb{Z}$ being adjacent if and only if $|i-j|\in D$. We present lower and upper bounds for ${\chi }_{\rho }(G(\mathbb{Z},D))$, showing that for finite $D$, the packing chromatic number is finite. Our main result concerns distance graphs with $D=\{1,t\}$ for which we prove some upper bounds on their packing chromatic numbers, the smaller ones being for $t\ge 447$: ${\chi }_{\rho }(G(\mathbb{Z},\{1,t\}))\le 40$ if $t$ is odd and ${\chi }_{\rho }(G(\mathbb{Z},\{1,t\}))\le 81$ if $t$ is even.

Cited by in corpus (6)

• Packing colorings of subcubic outerplanar graphs
• Packing chromatic number, $(1,1,2,2)$-colorings, and characterizing the Petersen graph
• Packing chromatic number under local changes in a graph
• Packing Chromatic Number of Distance Graphs
• Packing coloring of Sierpiński-type graphs
• $S$-packing colorings of distance graphs $G(\mathbb{Z},\{2,t\})$