Packing chromatic vertex-critical graphs

Abstract: The packing chromatic number

c h i_{h o} (G)

of a graph

G

is the smallest integer

k

such that the vertex set of

G

can be partitioned into sets

V_{i}

,

i i n [k]

, where vertices in

V_{i}

are pairwise at distance at least

i + 1

. Packing chromatic vertex-critical graphs,

c h i_{h o}

-critical for short, are introduced as the graphs

G

for which

c h i_{h o} (G - x) < c h i_{h o} (G)

holds for every vertex

x

of

G

. If

c h i_{h o} (G) = k

, then

G

is

k

-

c h i_{h o}

-critical. It is shown that if

G

is

c h i_{h o}

-critical, then the set

c h i_{h o} (G) - c h i_{h o} (G - x) : x i n V (G)

can be almost arbitrary. The

3

-

c h i_{h o}

-critical graphs are characterized, and

4

-

c h i_{h o}

-critical graphs are characterized in the case when they contain a cycle of length at least

5

which is not congruent to

0

modulo

4

. It is shown that for every integer

k g e 2

there exists a

k

-

c h i_{h o}

-critical tree and that a

k

-

c h i_{h o}

-critical caterpillar exists if and only if

k l e 7

. Cartesian products are also considered and in particular it is proved that if

G

and

H

are vertex-transitive graphs and

m d i a m (G) + m d i a m (H) l e c h i_{h o} (G)

, then

G, s q u a r e, H

is

c h i_{h o}

-critical.

Recommendations

Cited in

(9)

This page was built for publication: Packing chromatic vertex-critical graphs