Majority coloring games

Not scheduled
UP FHS (Koper)



Titov trg 5,Koper


Gabriel Jakóbczak (Jagiellonian University)


A vertex coloring of graph satisfies the *majority rule*, if for each vertex $v$ at most half of its neighbors receive the same color as $v$. A coloring which satisfies the majority rule is called *majority coloring*. The problem of such colorings was introduced in [1,5] and continued with different variants in [2,4]. We consider its game version. For given graph $G$ and color set $C$ two players, Alice and Bob, in alternating turns color vertices with respect to the majority rule. Alice wins when every vertex becomes colored, while goal for Bob is to create a vertex which cannot be colored with any color belonging to the set $C$ without breaking the majority rule. We show that if the color set $C$ is finite, there exists a graph $G$ on which Bob has winning strategy. Number of colors that Alice needs to have to win the game on graph $G$ is clearly bounded by game coloring number of $G$. We improve that bound for some classes of graphs. References: [1] R. Aharoni, E.C. Milner and K. Prikry, Unfriendly partitions of a graph. Journal Combinatorial Theory (series B) 50 (1990), 1--10. [2] M. Anholcer, B. Bosek and J. Grytczuk, Majority choosability of di-graphs. The Electronic Journal of Combinatorics 24 (3) (2017): #P3.57. [3] T. Bartnicki, J. Grytczuk, H. A. Kierstead and X. Zhu, The map-coloring game. American Mathematical Monthly 114 (2007), 793--803. [4] S. Kreutzer, S. Oum, P. Seymour, D. van der Zypen and D. R. Wood, Majority Closuring of Digraphs. arXiv:1608.03040 (2016). [5] S. Shelah and E.C. Milner, Graphs with no unfriendly partitions. A tribute to Paul Erd\"os, Cambridge University Press, Cambridge (1990), 373--384.

Primary authors

Dr Bartłomiej Bosek (Jagiellonian University) Gabriel Jakóbczak (Jagiellonian University) Prof. Jarosław Grytczuk (Warsaw University of Technology)

Presentation Materials

There are no materials yet.