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.
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.
Source: Wikipedia "Unfriendly partition" · CC BY-SA 4.0
Share this article: X · Bluesky