Kriesell's Conjecture ★★

Author(s): Kriesell

\begin{conjecture} Let $G$ be a graph and let $T\subseteq V(G)$ such that for any pair $u,v\in T$ there are $2k$ edge-disjoint paths from $u$ to $v$ in $G$. Then $G$ contains $k$ edge-disjoint trees, each of which contains $T$. \end{conjecture}

Keywords: Disjoint paths; edge-connectivity; spanning trees

Partitioning edge-connectivity ★★

Author(s): DeVos

\begin{question} Let $G$ be an $(a+b+2)$-\Def[edge-connected]{connectivity (graph theory)} graph. Does there exist a partition $\{A,B\}$ of $E(G)$ so that $(V,A)$ is $a$-edge-connected and $(V,B)$ is $b$-edge-connected? \end{question}

Keywords: edge-coloring; edge-connectivity

(2 + epsilon)-flow conjecture ★★★

Author(s): Goddyn; Seymour

\begin{conjecture} For every $\epsilon>0$ there exists an integer $k$ so that every $k$-\Def[edge-connected]{connectivity (graph theory)} graph has a $(2+\epsilon)$-flow. \end{conjecture}

Keywords: edge-connectivity; flow

Syndicate content