A simple competitive graph coloring algorithm III
A simple competitive graph coloring algorithm III
复制标题
DOI：
10.1016/j.jctb.2004.03.010
复制
发表时间：
2004-09
期刊：
影响因子：
--
通讯作者：
Charles L. Dunn;H. Kierstead
中科院分区：
文献类型：
--
作者：
Charles L. Dunn;H. Kierstead
我们考虑在有限图G上进行的以下对策：设r和d是正整数。两个玩家，爱丽丝和鲍勃，交替地用集合X中的颜色给G的顶点着色，|X|=r。如果通过用α∈给v着色，由颜色α的所有顶点诱导的子图至多具有最大度d，则对未着色的顶点v来说，颜色αX是合法的。每个玩家被要求在每一轮都合法地着色。如果图的所有顶点都合法着色，则Alice赢了游戏。如果有一天存在一个不能合法着色的未着色顶点，Bob将获胜。我们证明了如果G是平面的，则当r=3且d⩾132时，爱丽丝有获胜策略。我们还证明了，对于足够大的d，如果G是无4圈的平面图或围长至少为5的平面图，则当r=2时，Alice有获胜策略。
We consider the following game played on a finite graph G. Let r and d be positive integers. Two players, Alice and Bob, alternately color the vertices of G, using colors from a set X, with |X|=r. A color α∈X is legal for an uncolored vertex v if by coloring v with α, the subgraph induced by all vertices of color α has maximum degree at most d. Each player is required to color legally on each turn. Alice wins the game if all vertices of the graph are legally colored. Bob wins if there comes a time when there exists an uncolored vertex which cannot be legally colored. We show that if G is planar, then Alice has a winning strategy for this game when r=3 and d⩾132. We also show that for sufficiently large d, if G is a planar graph without a 4-cycle or with girth at least 5, then Alice has a winning strategy for the game when r=2.