1 Answers
In the mathematics of infinite graphs, an unfriendly partition or majority coloring is a partition of the vertices of the graph into disjoint subsets, so that every vertex has at least as many neighbors in other sets as it has in its own set. It is a generalization of the concept of a maximum cut for finite graphs, which is automatically an unfriendly partition. The unfriendly partition conjecture is an unsolved problem asking whether every countable graph has an unfriendly partition into two subsets.
5 views
Answered