Emerson, William R.

Unfriendly partitions ★★★

Author(s): Cowan; Emerson

If $G$ is a graph, we say that a partition of $V(G)$ is \emph{unfriendly} if every vertex has at least as many neighbors in the other classes as in its own.

\begin{problem} Does every countably infinite graph have an unfriendly partition into two sets? \end{problem}

Keywords: coloring; infinite graph; partition