Friendly partitions
Status partial high confidence
DeVos's question (equivalent to the internal-partition conjecture for $r$-regular graphs) remains open in full generality. Ban and Linial (2013) proved the conjecture for $r=6$ and exhibited new families of regular graphs without internal partitions; the cubic and 4-regular cases were already essentially known. The 5-regular case is still open as a deterministic statement, but Bärnkopf, Nagy and Paulovics (2024) settled it for 5-regular abelian Cayley graphs, and Csóka, Fekete, Nagy and Szemerédi (2025) showed that random 5-regular graphs a.a.s. admit an internal partition.
Cited literature (4)
-
Proves the internal/friendly partition conjecture for $r=6$ (all but finitely many 6-regular graphs have an internal partition), gives improved lower bounds on the threshold $N(d)$, and constructs new families of $d$-regular graphs without internal partitions, including $2k$-regular examples on $3k+2$ vertices.
-
Studies the still-open 5-regular case, classifies all 5-regular abelian Cayley graphs without an internal partition, and obtains structural results on subgraphs of minimum degree 3 inside 5-regular graphs.
-
Using a local-algorithm based factor with a recoloring phase, proves that random 5-regular graphs asymptotically almost surely admit an internal (friendly) partition, and derives new upper bounds on bisection width and max-cut of random $d$-regular graphs for $d>4$.
-
partial Majority Dynamics and Internal Partitions of Random Regular Graphs: Experimental Results (2024)
Investigates majority dynamics on random odd-regular graphs as a heuristic for producing internal partitions, shows the standard dynamics fails to yield parts with the required $\lceil d/2\rceil$-cores, and proposes a modified dynamics that does so with high probability.
Reviewer notes. DeVos's 'friendly partition' problem is exactly the internal-partition conjecture studied in the literature (vertex partition into two nonempty parts where every vertex has at least as many neighbours in its own part as in the other). The cases $r\in\{3,4\}$ are folklore/easy (cubic case reduces to two disjoint cycles, excluding $K_4$ and $K_{3,3}$). The Ban-Linial paper resolves $r=6$; $r=5$ and all $r\geq 7$ remain open in the deterministic sense, with progress only for random graphs and special families (Cayley graphs). The DOI 10.1007/s00373-024-02774-9 for the Graphs and Combinatorics version was found via search but the Springer page required authentication; the arXiv abstract page was verified directly.
Discussion
Let me say at the start, that I (M. DeVos) suspect this problem has been considered previously, so I await a more correct attribution. An unfriendly partition of a graph is a partition of the vertices into two sets so that every vertex has at least as many neighbours in the opposite class as its own. It is an easy fact that every (finite) graph has an unfriendly partition; for instance, any maximum size edge-cut gives a partition with this property. Finding friendly partitions appears to be considerably more difficult. Perhaps one reason why is that there exist graphs without unfriendly partitions. For instance, $ K_{2n} $ and $ K_{2n+1,2n+1} $ have no unfriendly partitions. However, it appears possible that the only graphs which fail to have friendly partitions are fairly dense. When $ r=3 $ , the above problem is fairly easy to solve, as it reduces to the problem of finding two vertex disjoint cycles. Every cubic graph other than $ K_4 $ or $ K_{3,3} $ has two disjoint cycles, and thus has a friendly partition. The case when $ r=4 $ is also not terribly complicated. However, the next step up, $ r=5 $ looks like a tricky problem which requires something new.