11 problems

Bounded-degree bisection conjecture. If $k$ is odd, then $G$ has a bisection of weight at least

Let $G$ be a random graph in the setting of the paper, and consider the property that $G$ has no forest cut, together with the property that every neighbourhood in $G$ contains a c…

Let $k$ be an integer, let $G$ be a graph with at least $k$ vertices, and let $X$ be one side of a cut of $G$. Write $V(G)$ and $E(G)$ for the vertex and edge sets, and let…

Let $G$ be an $n$-vertex graph. A bipartite cut is a cut whose induced subgraph on one side is bipartite. Bogdanov–Neustroeva–Sokolov–Volostnov–Russkin–Voronov conjecture. Any $n$-…

3-edge-cut conjecture. The Speyer polynomials satisfy

DeMarco–Kahn's conjecture. For every $p\gg \log n/n$, every maximum cut of $G_{n,p}$ divides the neighbourhood of every vertex into two parts, each of size $(1/2+o(1))np$, whp.

DeMarco–Kahn's conjecture. For all $p\gg \log n/n$, every maximum cut of $G_{n,p}$ whp divides the neighbourhood of every vertex into two parts of size $(1/2+o(1))np$.

Triangle-free subcubic bisection conjecture. Every weighted triangle-free subcubic graph other than $K_{1,3}$ has a bisection of weight at least

Gutin–Yeo conjecture. Every weighted triangle-free subcubic graph has a cut of weight at least

Non-crossing ELP-cut conjecture. If $C$ is a nontrivial tight cut of $G$, then $G$ has an ELP-cut that does not cross $C$.

Erdős's conjecture.