A simple competitive graph coloring algorithm III

摘要: We consider the following game played on a finite graph G. Let r and d be positive integers. Two players, Alice Bob, alternately color vertices of G, using colors from set X, with |X| = r. A α ∈ X is legal for an uncolored vertex v if by coloring α, subgraph induced all has maximum degree at most d. Each player required to legally each turn. wins are colored. Bob there comes time when exists which cannot show that G planar, then winning strategy this 3 ≥ 132. also sufficiently large d, planar without 4-cycle or girth least 5, 2.