IIT Jodhpur $\cdot$ Guided by Brahadeesh Sankarnarayanan
Majority Game Coloring of Trees:
A majority coloring of a graph is a vertex coloring in which each vertex has at most half of its neighbors sharing its color; Lovász showed in 1966 that two colors always suffice for any finite graph. In the majority coloring game, two players alternately color vertices from a fixed palette while maintaining the majority condition, and the least number of colors for which the first player has a winning strategy is the majority game chromatic number $\mu_g(G)$. While is unbounded in general, it is at most 4 for trees. We studied $\mu_g(T)$ trees using a configuration-based strategy, in which the first player aims to prevent a small family of local obstruction patterns from arising.
An interactive Tree Coloring Explorer is available for experimenting with the majority colorings on trees.