Emerson, William R.
Unfriendly partitions ★★★
If is a graph, we say that a partition of is unfriendly if every vertex has at least as many neighbors in the other classes as in its own.
Problem Does every countably infinite graph have an unfriendly partition into two sets?
Keywords: coloring; infinite graph; partition