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. (If not, a vertex with more neighbors in its own set could be moved to the other set, increasing the number of cut edges.) The unfriendly partition conjecture is an unsolved problem asking whether every countable graph has an unfriendly partition into two subsets. Robert H. Cowan and William R. Emerson, in unpublished work, conjectured that every infinite graph has an unfriendly partition into two subsets. However, Saharon Shelah and Eric Charles Milner disproved the conjecture, showing that uncountable graphs might not have two-subset unfriendly partitions. Nevertheless, they showed that an unfriendly partition into three subsets always exists. Among countable graphs, the existence of a two-subset unfriendly partition is known for the following special cases:
Graphs that have finitely many vertices of infinite degree
Graphs in which all vertices have infinite degree, by an argument using the back-and-forth method
Graphs with no end
Graphs without a subdivision of an infinite clique
The case for arbitrary countable graphs remains open. References

Graph theory objects
Infinite graphs
Unsolved problems in graph theory