  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 conjectured that every $d$-regular graph with $n>N(d)$
vertices has an internal partition. Here we prove this for $d=6$. The case
$d=n-4$ is of particular interest and leads to interesting new open problems on
cubic graphs. We also provide new lower bounds on $N(d)$ and find new families
of graphs with no internal partitions. Weighted versions of these problems are
considered as well.
