Trees of minimum order with game chromatic index equal ∆+1

Wai Hong CHAN

Research output: Contribution to journalArticlespeer-review


In an edge-coloring game, Alice and Bob take turns to pick one color in a given color set and put it on one of the uncolored edges of a graph G so that no adjacent edges will receive the same color. Bob makes the first move and he is allowed to skip his moves while Alice is not. Alice needs to color all the edges of G to win the game while Bob tries to make one uncolored edge surrounded by all colors in the given color on its adjacent edges. The least number of colors required in the given color set so that Alice can have a strategy to win the game on G is called the game chromatic index of G. It is known that, for most of trees, the game chromatic index is equal to their maximum degrees, ∆, or ∆+1. In this paper, we shall show that the minimum order of trees with game chromatic index equal to ∆+1 is 3∆-1. Copyright © 2014 Utilitas Mathematica Pub. Inc.
Original languageEnglish
Pages (from-to)151-160
JournalCongressus Numerantium
Publication statusPublished - 2014


Chan, W. H. (2014). Trees of minimum order with game chromatic index equal ∆+1. Congressus Numerantium, 219, 151-160.


  • Game chromatic index
  • Maximum degree
  • Tree


Dive into the research topics of 'Trees of minimum order with game chromatic index equal ∆+1'. Together they form a unique fingerprint.