regular

Friendly partitions ★★

Author(s): DeVos

A 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.

Problem Is it true that for every $r$ , all but finitely many $r$ -regular graphs have friendly partitions?

Keywords: edge-cut; partition; regular

Posted by mdevos
updated August 5th, 2020

1 comment

Graph Theory » Basic G.T.

Nearly spanning regular subgraphs ★★★

Author(s): Alon; Mubayi

Conjecture For every $\epsilon > 0$ and every positive integer $k$ , there exists $r_0 = r_0(\epsilon,k)$ so that every simple $r$ -regular graph $G$ with $r \ge r_0$ has a $k$ -regular subgraph $H$ with $|V(H)| \ge (1- \epsilon) |V(G)|$ .