Edge colouring Game on Trees with maximum degree $Δ=4$

Consider the following game. We are given a tree $T$ and two players (say) Alice and Bob who alternately colour an edge of a tree (using one of $k$ colours). If all edges of the tree get coloured, then Alice wins else Bob wins. Game chromatic index of trees of is the smallest index $k$ for which there is a winning strategy for Alice. If the maximum degree of a node in tree is $Δ$, Erdos et.al.[6], show that the game chromatic index is at least $Δ+1$. The bound is known to be tight for all values of $Δ\neq 4$. In this paper we show that for $Δ=4$, even if Bob is allowed to skip a move, Alice can always choose an edge to colour and win the game for $k=Δ+1$. Thus the game chromatic index of trees of maximum degree $4$ is also $5$. Hence, game chromatic index of trees of maximum degree $Δ$ is $Δ+1$ for all $Δ\geq 2$. Moreover,the tree can be preprocessed to allow Alice to pick the next edge to colour in $O(1)$ time. A result of independent interest is a linear time algorithm for on-line edge-deletion problem on trees.

No reviews yet.

No comments yet.