Internal Partitions of Regular Graphs

Amir Ban, Nati Linial

An internal partition of an $n$-vertex graph $G=(V,E)$ is a partition of $V$ such that every vertex has at least as many neighbors in its own part as in the other part. It has been…