# On Packing Colorings of Distance Graphs

Research paper by **Olivier Togni**

Indexed on: **20 Feb '14**Published on: **20 Feb '14**Published in: **Computer Science - Discrete Mathematics**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### 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,\ldots ,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\geq 447$:
$\chi_{\rho}(G(\mathbb{Z},\{1,t\}))\leq 40$ if $t$ is odd and
$\chi_{\rho}(G(\mathbb{Z},\{1,t\}))\leq 81$ if $t$ is even.