7 problems

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

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

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

Carvalho–Lucchesi–Murty conjecture. The graph $G$ has a nontrivial ELP cut that is laminar with $C$.

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