Skip to main content
Article
Packing chromatic number of distance graphs
Discrete Applied Mathematics (2012)
  • Jan Ekstein, University of West Bohemia
  • Přemysl Holub, University of West Bohemia
  • Bernard Lidicky, Iowa State University
Abstract
The packing chromatic number χρ(G) of a graph G is the smallest integer k such that vertices of G can be partitioned into disjoint classes X1,…,Xk where vertices in Xi have pairwise distance greater than i. We study the packing chromatic number of infinite distance graphs G(Z,D), 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|∈D.

In this paper we focus on distance graphs with D={1,t}. We improve some results of Togni who initiated the study. It is shown that χρ(G(Z,D))≤35 for sufficiently large odd t and χρ(G(Z,D))≤56 for sufficiently large even t. We also give a lower bound 12 for t≥9 and tighten several gaps for χρ(G(Z,D)) with small t.


Keywords
  • Distance graph,
  • Packing coloring,
  • Packing chromatic number
Publication Date
March, 2012
DOI
10.1016/j.dam.2011.11.022
Publisher Statement
This is a manuscript of an article published as Ekstein, Jan, Přemysl Holub, and Bernard Lidický. "Packing chromatic number of distance graphs." Discrete Applied Mathematics 160, no. 4 (2012): 518-524. DOI: 10.1016/j.dam.2011.11.022. Copyright 2011 Elsevier B.V. Posted with permission.
Citation Information
Jan Ekstein, Přemysl Holub and Bernard Lidicky. "Packing chromatic number of distance graphs" Discrete Applied Mathematics Vol. 160 Iss. 4-5 (2012) p. 518 - 524
Available at: http://works.bepress.com/bernard-lidicky/21/