Packing chromatic number of distance graphs

Abstract: The packing chromatic number

c h i_{h o} (G)

of a graph

G

is the smallest integer

k

such that vertices of

G

can be partitioned into disjoint classes

X_{1}, ..., X_{k}

where vertices in

X_{i}

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 i n Z

are adjacent if and only if

| i - j | i n 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

c h i_{h o} (G (Z, D)) l e q 35

for sufficiently large odd

t

and

c h i_{h o} (G (Z, D)) l e q 56

for sufficiently large even

t

. We also give a lower bound 12 for

t g e q 9

and tighten several gaps for

c h i_{h o} (G (Z, D))

with small

t

.

Recommendations

Cites Work

Cited In (14)

This page was built for publication: Packing chromatic number of distance graphs