完全多部图的指示选择数

Indicated Choosability of Complete Multipartite Graphs

摘要: 图 G 上的指示列表染色游戏由两名玩家 Ann 和 Ben 参与，最初每个点都未染色。每个回合 Ann 选择一个未染色的点 v，Ben 用 L(v) 中的一个颜色 c 给 v 染色且保证对相邻的两个点 u， v，它们染的颜色不能相同。若 G 能够被染好，则 Ann 获胜。反之，某一轮后存在一个未染色 的点 v 没有颜色可用，则 Ben 获胜。若 Ann 在指示列表染色游戏中有必胜策略，我们称 G 是 指示 L-可染的。若对 G 的任意一个大小为 k 的列表 L，都满足 G 是指示 L-可染的，我们称 G 是指示 k-可选的。满足 G 是指示 k-可选的最小的正整数 k 称 G 的指示选择数。在指示列表染 色游戏中赋予 Ann 一个权力，当选择一个点 v 后，可以禁掉 L(v) 中掉颜色 c，即禁止 Ben 用c 去染 v。若此时 Ann 有必胜策略，我们就称 G 是弱指示 L-可染的，我们定义图的弱指示选择 数为使得 G 是弱指示 k-可选的最小正整数 k。本文证明了完全多部图的指示选择数大于等于 n + 1 且等于 2n - 2。并证明了当 n = 3,4 时，完全多部图的弱指示选择数等于 n。

Abstract: The indicated L-coloring game on G is a game played by two players: Ann and Ben. Initially, every vertex is uncolored. In each round, Ann chooses an uncolored vertex v and Ben assigns to v a color c of L(v) and ensures that for any two adjacent points u,v, their colors must be different. Ann wins the game if all vertices of G are colored. Otherwise, after some rounds, there is an uncolored vertex v, all colors in L(v) are assigned to its colored neighbors, then Ben wins. We say G is indicated L-colorable if Ann has a winning strategy for the indicated L-coloring game. If for any list assignment L that |L(v)|=k for all v of V(G), G is indicated L-coloralble, we say G is indicated k-choosable. The indicated choice number of G is the minimum integer k for which G is indicated k-choosable. If in the indicated list coloring game, Ann is granted the power to forbid the color c from L(v) when she chooses an uncolored v, i.e., to prevent Ben from coloring v with c, and if Ann has a winning strategy under these conditions, we say G is weakly indicated L-colorable. Similarly, the weak indicated choice number of G is the minimum integer k for which G is weakly indicated k-choosable. In this paper we prove that for any multipartite graph G, its indicated choice number is at least n + 1 but at most 2n - 2. And for n = 3,4, the weak indicated choice number of G is n.