On packing colorings of distance graphs

Abstract: The {em packing chromatic number}

c h i_{h o} (G)

of a graph

G

is the least integer

k

for which there exists a mapping

f

from

V (G)

to

1, 2, l d o t s, 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 (m a t h b b Z, D)

, i.e. graphs with the set

m a t h b b Z

of integers as vertex set, with two distinct vertices

i, j i n m a t h b b Z

being adjacent if and only if

| i - j | i n D

. We present lower and upper bounds for

c h i_{h o} (G (m a t h b b 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 g e q 447

:

c h i_{h o} (G (m a t h b b Z, 1, t)) l e q 40

if

t

is odd and

c h i_{h o} (G (m a t h b b Z, 1, t)) l e q 81

if

t

is even.

Recommendations

Cites work

Cited in

(30)

This page was built for publication: On packing colorings of distance graphs