A majority coloring of a graph assigns colors to vertices so that each vertex has at most half of its neighbors in the same color class. This tool lets you experiment with majority colorings on trees. Click any vertex to cycle through the available colors. The goal is to find a valid majority coloring — one where for every vertex $v$, at most $\lfloor \deg(v)/2 \rfloor$ neighbors share $v$’s color — using as few colors as possible.
Select a tree type from the first dropdown and the number of colors from the second. Use Regenerate to draw a fresh random tree, or choose Your Tree to build a custom tree: click a node to select it, then use Add child and Delete to modify the tree, and Done when finished.
Built with Dr. Brahadeesh as a part of work on the majority coloring game on trees; see the research description for context.
A coloring is a valid majority coloring if, for every vertex \(v\), at most \(\lfloor \deg(v)/2 \rfloor\) neighbors of \(v\) share its color.