Relaxed very asymmetric coloring games
Relaxed very asymmetric coloring games
复制标题
轻松的非常不对称的着色游戏
DOI：
10.1016/j.disc.2007.11.058
复制
发表时间：
2009-03
影响因子：
0.8
通讯作者：
Yang, Daqing
中科院分区：
文献类型：
--
作者：
Yang, Daqing
This paper investigates a competitive version of the coloring game on a finite graph G. An asymmetric variant of the (r,d)-relaxed coloring game is called the (r,d)-relaxed (a,b)-coloring game. In this game, two players, Alice and Bob, take turns coloring the vertices of a graph G, using colors from a set X, with |X|=r. On each turn Alice colors a vertices and Bob colors b vertices. A color α∈X is legal for an uncolored vertex u if by coloring u with color α, the subgraph induced by all the vertices colored with α has maximum degree at most d. Each player is required to color an uncolored vertex legally on each move. The game ends when there are no remaining uncolored vertices. Alice wins the game if all vertices of the graph are legally colored, Bob wins if at a certain stage there exists an uncolored vertex without a legal color. The d-relaxed (a,b)-game chromatic number, denoted by (a,b)-χgd(G), of G is the least r for which Alice has a winning strategy in the (r,d)-relaxed (a,b)-coloring game. The (r,d)-relaxed (1,1)-coloring game has been well studied and there are many interesting results. For the (r,d)-relaxed (a,1)-coloring game, this paper proves that if a graph G has an orientation with maximum outdegree k and a≥k, then (a,1)-χgd(G)≤k+1 for all d≥k2+2k; If a≥k3, then (a,1)-χgd(G)≤k+1 for all d≥2k+1.
登录
查看更多内容
影响因子：
0.9
作者：
H. Kierstead
通讯作者：
H. Kierstead
DOI：
10.1006/jctb.1998.1878
发表时间：
1999-03
期刊：
J. Comb. Theory B
影响因子：
--
作者：
Xuding Zhu
通讯作者：
Xuding Zhu
DOI：
10.1016/j.disc.2003.08.006
发表时间：
2004-04
期刊：
Discret. Math.
影响因子：
--
作者：
Wenjie He;Jiaojiao Wu;Xuding Zhu
通讯作者：
Wenjie He;Jiaojiao Wu;Xuding Zhu
DOI：
10.1016/j.jctb.2004.03.010
发表时间：
2004-09
期刊：
J. Comb. Theory B
影响因子：
--
作者：
Charles L. Dunn;H. Kierstead
通讯作者：
Charles L. Dunn;H. Kierstead
DOI：
10.1016/s0012-365x(02)00521-6
发表时间：
2003-02
期刊：
Discret. Math.
影响因子：
--
作者：
Chun-Yen Chou;Weifan Wang;Xuding Zhu
通讯作者：
Chun-Yen Chou;Weifan Wang;Xuding Zhu