Friendly partitions ★★

Author(s): DeVos

A \emph{friendly} partition of a graph is a partition of the vertices into two sets so that every vertex has at least as many neighbours in its own class as in the other.

\begin{problem} Is it true that for every $r$, all but finitely many $r$-regular graphs have friendly partitions? \end{problem}

Keywords: edge-cut; partition; regular

Syndicate content