{"id":"arxiv/2609.37796","url":"https://arxiv.org/abs/2609.37796","tags":["math.CO","cs.DM"],"score":0,"title":"Structural and computational aspects of majority coloring games","domain":"math.CO","source":"arxiv","authors":["Yash Chawda","Saraswati Girish Nanoti","Brahadeesh Sankarnarayanan","Eshwar Srinivasan"],"reviews":0,"subject":"math.CO","summary":"A majority coloring of a graph $G = (V,E)$ is a coloring of $V(G)$ such that, for each vertex $v$, the number of neighbors of $v$ with the same color as $v$ is at most $deg(v)/2$. A strong majority coloring is a coloring of $V(G)$ such that, for each vertex $v$, every monochromatic subset of $N(v)$ has size at most $deg(v)/2$. The (strong) majority coloring game is a two-player Maker-Breaker-type game, in which two players Alice and Bob color the vertices of a graph $G$ alternately, maintaining the (strong) majority condition. The least number of colors such that Alice has a winning strategy…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-29","reactions":{}}