Tree Coloring Explorer

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 and cycles. 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 graph type from the first dropdown and the number of colors from the second. Use Regenerate to draw a fresh random tree, choose Your Tree to build a custom tree, or choose Cycle (C_n), Path (P_n), or Caterpillar and set \(n\) to explore that family. 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 by Yash Chawda (Ph.D. student, IIT Jodhpur) as part of ongoing work on the majority coloring game on trees; see the research description for context.