Speaker
Gabriel Jakóbczak
(Jagiellonian University)
Description
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)
