
arXiv: 1011.0971
The {\em packing chromatic number} $��_��(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 $��_��(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$: $��_��(G(\mathbb{Z},\{1,t\}))\leq 40$ if $t$ is odd and $��_��(G(\mathbb{Z},\{1,t\}))\leq 81$ if $t$ is even.
FOS: Computer and information sciences, Distance in graphs, Discrete Mathematics (cs.DM), distance graph, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], packing chromatic number, Coloring of graphs and hypergraphs, graph coloring, FOS: Mathematics, Mathematics - Combinatorics, distance graph., Combinatorics (math.CO), Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Distance in graphs, Discrete Mathematics (cs.DM), distance graph, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], packing chromatic number, Coloring of graphs and hypergraphs, graph coloring, FOS: Mathematics, Mathematics - Combinatorics, distance graph., Combinatorics (math.CO), Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 16 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
