### Abstract

Let

*X*∈ {*A*,*B*} and*Y*∈ {*A*,*B*,*−*} , where*A*,*B*and*−*denote (player) Alice, (player) Bob and none of the players, respectively. In the*k-*[*X*,*Y*]-edge-coloring game, Alice and Bob alternately choose a color from a given color set with*k*colors to color an uncolored edge of a graph*G*such that no adjacent edges receive the same color. Player*X*begins and Player*Y*has the right to skip any number of turns. Alice wins the game if all the edges of*G*are finally colored; otherwise, Bob wins. The [*X*,*Y*]-game chromatic index of an uncolored graph*G*, denoted by χ’_{[X,Y] }(*G*), is the least*k*such that Alice has a winning strategy for the game. We prove that, for any [*X*,*Y*], Alice has a winning strategy for the*k-*[*X*,*Y*]-edge-coloring game on any tree*T*when*k*>*χ’*(T). Moreover, using some parts of the proofs of the above results, we show that there is a tree_{[X,Y] }*T*satisfying*χ’*(_{[A,−]}*T*) <*χ’*_{[B,−]}_{ }(*T*) and*χ’*_{[A,−]}_{ }(*T*−*e*) <*χ’*_{[B,−]}_{ }(*T*−*e*) for some edge*e*of*T*. This solves an open problem proposed by Andres et al. (Discrete Appl Math 159:1660–1665, 2011). Copyright © 2019 Springer Science+Business Media, LLC, part of Springer Nature.Original language | English |
---|---|

Pages (from-to) | 456-480 |

Journal | Journal of Combinatorial Optimization |

Volume | 38 |

Issue number | 2 |

Early online date | 19 Feb 2019 |

DOIs | |

Publication status | Published - Aug 2019 |

### Citation

Fong, W. L., & Chan, W. H. (2019). The edge coloring game on trees with the number of colors greater than the game chromatic index. Journal of Combinatorial Optimization, 38(2), 456-480. doi: 10.1007/s10878-019-00395-0### Keywords

- Game chromatic index
- Game chromatic number
- Graph coloring game
- Tree
- Line graph
- PG student publication