The packing coloring of distance graphs D(k,t)

Abstract: The packing chromatic number

c h i_{h o} (G)

of a graph

G

is the smallest integer

p

such that vertices of

G

can be partitioned into disjoint classes

X_{1}, ..., 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

of integers as vertex set and in which two distinct vertices

are adjacent if and only if

| i - j | i n k, t

. We generalize results by Ekstein et al. for graphs

D (1, t)

. For sufficiently large

t

we prove that

c h i_{h o} (D (k, t)) l e q 30

for both

k

,

t

odd, and that

c h i_{h o} (D (k, t)) l e q 56

for exactly one of

k

,

t

odd. We also give some upper and lower bounds for

c h i_{h o} (D (k, t))

with small

k

and

t

. Keywords: distance graph; packing coloring; packing chromatic number

Recommendations

Cites Work

Cited In (23)

This page was built for publication: The packing coloring of distance graphs \(D(k,t)\)