Unfriendly partitions of locally finite Borel graphs
When mathematicians can't color a graph fairly, no matter how they try
A mathematician has solved a long-standing question by proving that some infinitely large networks cannot be split into two groups where no group contains all neighbors of any single point—a property called an unfriendly partition. However, the paper also shows that networks with maximum degree four (where each point connects to at most four others) can always be split this way if they have certain structural features like cycles.
Graph coloring problems appear in scheduling, map coloring, and conflict resolution algorithms. Understanding when fair partitions are and aren't possible helps computer scientists know which real-world network problems have solutions and which don't, preventing wasted effort on impossible tasks.