The Packing Coloring of Distance Graphs D(k,t)

2013/02/04 by Jan Ekstein, Ekstein, Jan, Přemysl Holub +3
Mathematics · #(2010): 05C12 #05C15 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C12 #msc:05C15

paper · pdf · doi:10.48550/arxiv.1302.0721

15 pages

arxiv created 2013/02/04 · arxiv updated 2013/02/05

Abstract

The packing chromatic number χ_ρ(G) of a graph G is the smallest integer p such that vertices of G can be partitioned into disjoint classes X₁, ..., X_p where vertices in X_i have pairwise distance greater than i. For k < t we study the packing chromatic number of infinite distance graphs D(k, t), i.e. graphs with the set \Z of integers as vertex set and in which two distinct vertices i, j ∈ \Z are adjacent if and only if |i - j| ∈ \k, t\. We generalize results by Ekstein et al. for graphs D (1, t). For sufficiently large t we prove that χ_ρ(D(k, t)) ≤ 30 for both k, t odd, and that χ_ρ(D(k, t)) ≤ 56 for exactly one of k, t odd. We also give some upper and lower bounds for χ_ρ(D(k, t)) with small k and t. Keywords: distance graph; packing coloring; packing chromatic number

Related

• Packing Chromatic Number of Distance Graphs
• S-packing colorings of distance graphs G(ℤ,\2,t\)
• S-packing colorings of distance graphs with distance sets of cardinality 2
• The packing chromatic number of the square lattice is at least 12
• On packing total coloring