Indicated coloring of matroids
Indicated coloring of matroids
复制标题
拟阵的指示颜色
DOI：
10.1016/j.dam.2014.07.004
复制
发表时间：
2013
影响因子：
1.1
通讯作者：
Michal Lason
中科院分区：
文献类型：
--
作者：
Michal Lason
如果具有相同颜色的元素组成一个独立的集合，则拟阵的着色是适当的。对于无环拟阵M，它的色数χ(M)是M的真染色的最小色数。在本文中，我们研究了Grytczuk提出的这个参数的博弈论变体。在游戏的每一轮中，Alice指示一个未着色的仍然元素，然后Bob使用固定的一组颜色C中的一种颜色对其进行适当的着色。如果整个拟阵是着色的，或者如果Bob到达了不能正确扩展的部分着色，则游戏结束。爱丽丝在第一场比赛中获胜，而鲍勃在第二场比赛中获胜。由χI(M)表示的M的所指示的色数是爱丽丝对其具有获胜策略的颜色集合C的最小尺寸。证明了对于每一个无环拟阵M，都有一个等式χI(M)=χ(M)。
A coloring of a matroid is proper if elements of the same color form an independent set. For a loopless matroid M, its chromatic number χ (M) is the minimum number of colors in a proper coloring of M. In this note we study a game-theoretic variant of this parameter proposed by Grytczuk. In each round of the game Alice indicates an uncolored yet element, then Bob colors it properly using a color from a fixed set of colors C. The game ends if the whole matroid is colored or if Bob arrives at a partial coloring that cannot be properly extended. Alice wins in the first case, while Bob in the second. The indicated chromatic number of M, denoted by χ i (M), is the minimum size of the set of colors C for which Alice has a winning strategy. We prove that for every loopless matroid M there is an equality χ i (M)= χ (M).