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

Nearly spanning regular subgraphs ★★★

Author(s): Alon; Mubayi

\begin{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)|$. \end{conjecture}

Keywords: regular; subgraph

r-regular graphs are not uniquely hamiltonian. ★★★

Author(s): Sheehan

\begin{conjecture} If $G$ is a finite $r$-regular graph, where $r > 2$, then $G$ is not uniquely hamiltonian. \end{conjecture}

Keywords: hamiltonian; regular; uniquely hamiltonian

Syndicate content