The edge coloring game on trees with the number of colors greater than the game chromatic index

Wai Lam FONG, Wai Hong CHAN

Research output: Contribution to journalArticles

Abstract

Let ∈ {A, B} and ∈ {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 > χ’[X,Y] (T). Moreover, using some parts of the proofs of the above results, we show that there is a tree T satisfying χ’[A,−] (T) < χ’[B,−] (T) and χ’[A,−] (Te) < χ’[B,−] (Te) 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 languageEnglish
Pages (from-to)456-480
JournalJournal of Combinatorial Optimization
Volume38
Issue number2
Early online date19 Feb 2019
DOIs
Publication statusPublished - 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

Fingerprint Dive into the research topics of 'The edge coloring game on trees with the number of colors greater than the game chromatic index'. Together they form a unique fingerprint.