On game chromatic vertex-critical graphs

Abstract: Several games that arise from graph coloring have been introduced and studied. Let

v a r p h i

denote a graph invariant that arises from such a game. If

G

is a graph and

v a r p h i (G - x) e q v a r p h i (G) = k

,

k g e q 1

, holds true for every vertex

x i n V (G)

, then

G

is called a

k

-

v a r p h i

-game-vertex-critical graph. We study the concept of

v a r p h i

-game-vertex-criticality for

v a r p h i i n c h i_{g}, c h i_{i}, c h i_{i g}^{A}, c h i_{i g}^{A B}

, where

c h i_{g}

denotes the standard game chromatic number,

c h i_{i}

denotes the indicated game chromatic number and

c h i_{i g}^{A}

,

c h i_{i g}^{A B}

denote two versions of the independence game chromatic number. Since the game chromatic number

v a r p h i (G - x)

can either decrease or increase with respect to

v a r p h i (G)

, we distinguish between lower, upper and mixed vertex-criticality. We show that for

v a r p h i i n c h i_{g}, c h i_{i g}^{A}, c h i_{i g}^{A B}

the difference

v a r p h i (G) - v a r p h i (G - x)

,

x i n V (G)

, can be arbitrarily large. A characterization of

2

-

v a r p h i

-game-vertex-critical and (connected)

3

-

v a r p h i

-lower-game-vertex-critical graphs for all

v a r p h i i n c h i_{g}, c h i_{i}, c h i_{i g}^{A}, c h i_{i g}^{A B}

is given. It is shown that

c h i_{g}

-game-vertex-critical,

c h i_{i g}^{A}

-game-vertex-critical and

c h i_{i g}^{A B}

-game-vertex-critical graphs are not necessarily connected. However, it is also shown that

c h i_{i}

-lower-game-vertex-critical graphs are always connected.

Recommendations

Cites work

Cited in

(1)

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