Premium
Game chromatic index of k ‐degenerate graphs
Author(s) -
Cai Leizhen,
Zhu Xuding
Publication year - 2001
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/1097-0118(200103)36:3<144::aid-jgt1002>3.0.co;2-f
Subject(s) - mathematics , combinatorics , chromatic scale , degenerate energy levels , index (typography) , edge coloring , graph , discrete mathematics , computer science , line graph , physics , graph power , quantum mechanics , world wide web
We consider the following edge coloring game on a graph G . Given t distinct colors, two players Alice and Bob, with Alice moving first, alternately select an uncolored edge e of G and assign it a color different from the colors of edges adjacent to e . Bob wins if, at any stage of the game, there is an uncolored edge adjacent to colored edges in all t colors; otherwise Alice wins. Note that when Alice wins, all edges of G are properly colored. The game chromatic index of a graph G is the minimum number of colors for which Alice has a winning strategy. In this paper, we study the edge coloring game on k ‐degenerate graphs. We prove that the game chromatic index of a k ‐degenerate graph is at most Δ + 3 k − 1, where Δ is the maximum vertex degree of the graph. We also show that the game chromatic index of a forest of maximum degree 3 is at most 4 when the forest contains an odd number of edges. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 144–155, 2001