The Relaxed Edge-Coloring Game and k-Degenerate Graphs

被引：0
作者：
Charles Dunn
David Morawski
Jennifer Firkins Nordstrom
机构：
[1] Linfield College,
[2] University of Minnesota,undefined
来源：
Order | 2015年 / 32卷
关键词：
Competitive coloring; -degenerate graph; Edge coloring;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
The (r, d)-relaxed edge-coloring game is a two-player game using r colors played on the edge set of a graph G. We consider this game on forests and more generally, on k-degenerate graphs. If F is a forest with Δ(F)=Δ, then the first player, Alice, has a winning strategy for this game with r=Δ−j and d≥2j+2 for 0≤j≤Δ−1. This both improves and generalizes the result for trees in Dunn, C. (Discret. Math. 307, 1767–1775, 2007). More broadly, we generalize the main result in Dunn, C. (Discret. Math. 307, 1767–1775, 2007) by showing that if G is k-degenerate with Δ(G)=Δ and j∈[Δ+k−1], then there exists a function h(k,j) such that Alice has a winning strategy for this game with r=Δ+k−j and d≥h(k,j).
引用
收藏
页码：347 / 361
页数：14
相关论文
共 47 条
  • [1] Andres SD(2006)The game chromatic index of forests of maximum degree ##Δ##≥5 Discret. Appl. Math. 154 1317-1323
  • [2] Cai L(2001)Game chromatic index of k-degenerate graphs J. Graph Theory 36 144-155
  • [3] Zhu X(2003)Relaxed game chromatic number of graphs Discret. Math. 262 89-98
  • [4] Chou C(1986)Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency J. Graph Theory 10 187-195
  • [5] Wang W(1997)Defective coloring revisited J. Graph Theory 24 205-220
  • [6] Zhu X(1998)Relaxed coloring of a graph Graphs Combin. 14 121-130
  • [7] Cowen L(1999)A bound for the game chromatic number of graphs Discret. Math. 196 109-115
  • [8] Cowen R(2012)Complete multipartite graphs and the relaxed coloring game Order 29 507-512
  • [9] Woodall D(2007)The relaxed game chromatic index of k-degenerate graphs Discret. Math. 307 1767-1775
  • [10] Cowen L(2004)A simple competitive graph coloring algorithm II J. Comb. Theory Series B 90 93-106
12345