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

Research output: Contribution to journalArticles

Abstract

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
Volume219
Publication statusPublished - 2014

Citation

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

Keywords

  • Game chromatic index
  • Maximum degree
  • Tree

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