Access Restriction

Author Togni, Olivier
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Distance Graph ♦ Packing Coloring ♦ Chromatic Number ♦ Packing Chromatic Number ♦ Upper Bound ♦ Infinite Distance Graph ♦ Main Result Concern Distance Graph ♦ Paper Study ♦ Distinct Vertex
Abstract The 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,..., k} such that any two vertices of color i are at a distance of at least i+1. This paper studies the packing chromatic number of infinite distance graphs G(Z, D), i.e. graphs with the set Z of integers as vertex set, with two distinct vertices i, j ∈ Z being adjacent if and only if i − j ∈ D. We present lower and upper bounds for χρ(G(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 ≥ 447: χρ(G(Z, {1, t})) ≤ 40 if t is odd and χρ(G(Z, {1, t})) ≤ 81 if t is even.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2010-01-01