路和圈卡氏积的指示可选性

Indicated Choosability of Cartesian Products of Paths and Cycles

摘要: 图 G 上的指示列表染色游戏由两名玩家 Ann 和 Ben 来进行。一开始每个顶点都是未被染色的。 在每一轮中，Ann 都选择一个未染色的顶点，Ben 用该顶点的列表中的一个还没有给其已染色的 邻居使用过的颜色 c 给该顶点染色。如果 G 能够被染好，那么 Ann 获胜。反之，在某一轮后， 存在一个未染色的顶点，但是它的邻居已经把其列表中的所有颜色都使用了，则 Ben 获胜。如果 Ann 在指示列表染色游戏中有必胜策略，我们称 G 是指示 L-可染的。若 G 的任意一个大小为 k 的列表安排 L，都满足 G 是指示 L-可染的，我们称 G 是指示 k-可选的。满足 G 是指示 k-可 选的最小的正整数 k 称 G 的指示选择数。我们在指示列表染色游戏里再添一条游戏规则：在每 一轮中，Ann 有权在选择一个顶点后，禁止 Ben 使用该点列表中的一个颜色。若 Ann 有必胜 策略，称 G 是弱指示 L-可染的。类似指示选择数，我们也能定义弱指示选择数。本文证明了奇 圈和一条长度小于等于 3 的路形成的卡氏积的指示选择数为 3，并证明了任意长度的圈和长度大 于等于 3 的路形成的卡氏积的弱指示选择数为 3。

Abstract: The indicated L-coloring game on G is played by two players: Ann and Ben. Initially, every vertex is uncolored. In each round, Ann chooses an uncolored vertex and Ben assigns to this vertex a color c which has not been assigned to any of its colored neighbors. Ann wins the game if all vertices of G are colored. Otherwise, after some rounds, there is an uncolored vertex , all colors in its list are assigned to its colored neighbors, then Ben wins. We say G is indicated L-colourable if Ann has a winning strategy for the indicated L-colouring game. We say G is indicated k-choosable if G is indicated L-colourable for each k-list assignment L. The indicated choice number of G is the minimum integer k for which G is indicated k-choosable. We add a new rule to the indicated list colouring game. In each round, Ann has the right to choose a vertex and then prohibit Ben from using one color in its list. If Ann has a winning strategy, then we say G is weakly indicated L-colourable. Similar to the indicated choice number, we can also define the weak indicated choice number of G. In this paper, we prove that the indicated choice number of the Cartesian product formed by an odd cycle and a path of length no more than 3 is 3. And we prove that the weak indicated choice number of the Cartesian product formed by any cycle and a path of length greater than or equal to 3 is 3.