Activation strategy for relaxed asymmetric coloring games
Activation strategy for relaxed asymmetric coloring games
复制标题
轻松的非对称着色游戏的激活策略
DOI：
10.1016/j.disc.2008.09.047
复制
发表时间：
2009-05
影响因子：
0.8
通讯作者：
Yang, Daqing
中科院分区：
文献类型：
--
作者：
Yang, Daqing
本文研究了有限图g上的一种竞争型的着色博弈。(r,d)-松弛着色博弈的非对称变体称为(r,d)-松弛(a,b)-着色博弈。在这个游戏中，两个玩家Alice和Bob轮流给图G的顶点上色，使用集合X中的颜色，其中|X|=r。每次Alice给一个顶点上色，Bob给b个顶点上色。如果用颜色α给u上色，那么所有用α上色的顶点所形成的子图的最大度数不超过d，那么对于未上色的顶点u，颜色α∈X是合法的。每个玩家在每次移动中都需要合法地给未上色的顶点上色。当没有剩余未着色的顶点时，游戏结束。如果图中的所有顶点都合法上色，则Alice获胜，如果在某一阶段存在一个没有合法上色的顶点，则Bob获胜。G的d-relax (a,b)-game chromatic number，记作(a,b)-χgd(G)，是Alice在(r,d)-relax (a,b)-coloring game中具有制胜策略的最小r。本文将已有研究的着色游戏激活策略推广到放松的非对称着色游戏。然后将扩展策略应用于平面图、偏k树和(s,t)-伪偏k树上的(r,d)-松弛(a,1)-上色博弈。本文证明了对于平面图G，如果a≥2，则对于所有d≥77，则(a,1)-χgd(G)≤6。若H是偏k树，且1≤a<k，则(a,1)-χgd(H)≤k+1，对于所有d≥2k+2k−1a。如果H (s, t) -pseudo-partial k-tree,≥1,让φ(s t, k) = (1 + 1) (k2 + sk + tk +圣+ k + t + 1) + k + t,然后(a, 1)——χgd (H)≤k + 1对所有d≥φ(s t, k)。对于平面图G和a≥1，(a,1)-χgd(G)≤3对于所有d≥71+61a。这些结果将相应的(r,d)-松弛(1,1)-着色博弈结果推广到更广义的不对称情况。
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 of G, denoted (a,b)-χgd(G), is the least r for which Alice has a winning strategy in the (r,d)-relaxed (a,b)-coloring game. This paper extends the well-studied activation strategy of coloring games to relaxed asymmetric coloring games. The extended strategy is then applied to the (r,d)-relaxed (a,1)-coloring games on planar graphs, partial k-trees and (s,t)-pseudo-partial k-trees. This paper shows that for planar graphs G, if a≥2, then (a,1)-χgd(G)≤6 for all d≥77. If H is a partial k-tree, 1≤a<k, then (a,1)-χgd(H)≤k+1 for all d≥2k+2k−1a. If H is an (s,t)-pseudo-partial k-tree, a≥1, let φ(s,t,k,a)=(1+1a)(k2+sk+tk+st+k+t+1)+k+t, then (a,1)-χgd(H)≤k+1 for all d≥φ(s,t,k,a). For planar graphs G and a≥1, (a,1)-χgd(G)≤3 for all d≥71+61a. These results extend the corresponding (r,d)-relaxed (1,1)-coloring game results to more generalized asymmetric cases.
登录
查看更多内容
影响因子：
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.jctb.2007.04.004
发表时间：
2008
期刊：
J. Comb. Theory B
影响因子：
--
作者：
Xuding Zhu
通讯作者：
Xuding Zhu
DOI：
10.1090/dimacs/009/08
发表时间：
1994-10
期刊：
--
影响因子：
--
作者：
H. Kierstead;W. T. Trotter
通讯作者：
H. Kierstead;W. T. Trotter
DOI：
10.1016/j.disc.2003.08.006
发表时间：
2004-04
期刊：
Discret. Math.
影响因子：
--
作者：
Wenjie He;Jiaojiao Wu;Xuding Zhu
通讯作者：
Wenjie He;Jiaojiao Wu;Xuding Zhu