Incidence Coloring Game and Arboricity of Graphs

An incidence of a graph

G

is a pair (

v

,

e

) where

v

is a vertex of

G

and

e

an edge incident to

v

. Two incidences (

v

,

e

) and (

w

,

f

) are adjacent whenever

v

 = 

w

, or

e

 = 

f

, or

vw

 = 

e

or

f

. The incidence coloring game [S.D. Andres, The incidence game chromatic number, Discrete Appl. Math. 157 (2009), 1980–1987] is a variation of the ordinary coloring game where the two players, Alice and Bob, alternately color the incidences of a graph, using a given number of colors, in such a way that adjacent incidences get distinct colors. If the whole graph is colored then Alice wins the game otherwise Bob wins the game. The incidence game chromatic number

i

g

(

G

) of a graph

G

is the minimum number of colors for which Alice has a winning strategy when playing the incidence coloring game on

G

.

Andres proved that

$i_g(G) \le 2\varDelta(G) + 4k - 2$

for every

k

-degenerate graph

G

. We show in this paper that

$i_g(G) \le \lfloor\frac{3\varDelta(G) - a(G)}{2}\rfloor + 8a(G) - 2$

for every graph

G

, where

a

(

G

) stands for the arboricity of

G

, thus improving the bound given by Andres since

a

(

G

) ≤ 

k

for every

k

-degenerate graph

G

. Since there exists graphs with

$i_g(G) \ge \lceil\frac{3\varDelta(G)}{2}\rceil$

, the multiplicative constant of our bound is best possible.