论文标题
在树上的边缘着色游戏，最大程度$δ= 4 $
Edge colouring Game on Trees with maximum degree $Δ=4$
论文作者
论文摘要
考虑以下游戏。给我们一个树$ t $，两个玩家（Say）爱丽丝和鲍勃交替着色树的边缘（使用$ k $颜色之一）。如果树的所有边缘都变色了，那么爱丽丝将赢得其他鲍勃获胜。 “树木的游戏色索引”是最小的索引$ k $，为爱丽丝制定了胜利策略。如果树中的最大节点为$δ$，Erdos等人[6]，则表明游戏色索引至少为$δ+1 $。已知该界限对于所有$δ\ neq 4 $的值都很紧。 在本文中，我们表明，即使允许鲍勃（Bob）跳过搬家，但爱丽丝（Alice）也可以选择边缘上色并以$ k =δ+1 $赢得游戏。因此，最高度$ 4 $的树木的游戏色指数也是$ 5 $。因此，所有$δ\ geq 2 $的最高树木树的游戏色索引为$δ+1 $。 此外，可以对树进行预处理，以使爱丽丝在$ O（1）$时间中选择下一个边缘。 独立兴趣的结果是树上在线边缘缺失问题的线性时间算法。
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.
