论文标题
具有受限双色子图的图形着色：ii。图形游戏
Graph colorings with restricted bicolored subgraphs: II. The graph coloring game
论文作者
论文摘要
我们考虑图形着色游戏，其中两个玩家轮流适当地着色图形的顶点，一个玩家试图完成适当的着色，另一个玩家试图防止适当的颜色。我们表明，如果图$ g $具有适当的着色，其中每个物种子图的游戏着色数是有限的，那么$ g $的游戏变色数是有限的。作为此结果的推论，我们表明，对于两个图表$ g_1 $和$ g_2 $，带有有界的游戏颜色，笛卡尔产品$ g_1 \ square g_2 $具有有界的游戏色号，回答了X. Zhu的问题。我们还获得了强力的游戏色度上的上限，$ g_1 \ boxtimes g_2 $ of两个图。
We consider the graph coloring game, a game in which two players take turns properly coloring the vertices of a graph, with one player attempting to complete a proper coloring, and the other player attempting to prevent a proper coloring. We show that if a graph $G$ has a proper coloring in which the game coloring number of each bicolored subgraph is bounded, then the game chromatic number of $G$ is bounded. As a corollary to this result, we show that for two graphs $G_1$ and $G_2$ with bounded game coloring number, the Cartesian product $G_1 \square G_2$ has bounded game chromatic number, answering a question of X. Zhu. We also obtain an upper bound on the game chromatic number of the strong product $G_1 \boxtimes G_2$ of two graphs.
