Edge colouring Game on Trees with maximum degree Δ=4
share
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 Δ≠ 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 Δ≥ 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.
READ FULL TEXT