Computer Science – Discrete Mathematics
Scientific paper
2010-11-03
Computer Science
Discrete Mathematics
Scientific paper
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,...,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.
No associations
LandOfFree
On Packing Colorings of Distance Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Packing Colorings of Distance Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Packing Colorings of Distance Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-603863