The game chromatic index of some trees of maximum degree 4

Wai Hong CHAN, Ge NONG

Research output: Contribution to journalArticles

2 Citations (Scopus)

Abstract

The edge-coloring game on a graph with a given color set is a two-player game, in which Alice and Bob take turns (with Bob allowed to skip) to color an uncolored edge with a color from the given color set not assigned to any adjacent edges. Alice wins the game if all the edges of the graph are colored, while Bob wins if some uncolored edge does not have an available color. The game chromatic index of a graph G, , is the minimal cardinality of the given set of colors so that Alice has a winning strategy. It was proven that for any forest F of maximum degree Δ≠4, and the bound is sharp. The case of Δ=4 is still open. In this paper, we shall show that this bound, Δ+1, is also valid for the game chromatic index of forests of maximum degree 4 provided that each of their components is a caterpillar or contains no adjacent 4-vertices (vertices of degree 4). Copyright © 2014 Elsevier B.V.
Original languageEnglish
Pages (from-to)1-6
JournalDiscrete Applied Mathematics
Volume170
DOIs
Publication statusPublished - Jun 2014

Citation

Chan, W. H., & Nong, G. (2014) The game chromatic index of some trees of maximum degree 4. Discrete Applied Mathematics, 170, 1-6.

Keywords

  • Game chromatic index
  • Caterpillar
  • Tree
  • Graph coloring game
  • Game chromatic number

Fingerprint Dive into the research topics of 'The game chromatic index of some trees of maximum degree 4'. Together they form a unique fingerprint.