7 problems

Kawarabayashi–Ozeki conjecture. There exists a function $f(k,l)$ such that, for every $f(k,l)$-connected graph $G$ and two distinct vertices $s$ and $t$ in $G$, there are $k$ inter…

Let $(G,R)$ be an annotated graph, let $k$ be the number of terminal pairs, and write … Here $f$ denotes a computable function, and $|G|$ denotes the size of $G$. XP tractability c…

Let a digraph be given together with $k$ terminal pairs. A collection of paths is half-integral if every vertex belongs to at most two paths. Giannopoulou–Kawarabayashi–Kreutzer–Kr…

Disjoint-path connectivity conjecture. The maximum number of disjoint paths between any two permutations $\sigma$ and $\rho$ in $G$ equals $\min\{\deg(\sigma),\deg(\rho)\}$. This w…

Relaxed coarse Menger conjecture. For all $k,d$ there exist $\ell,n$ such that, if $S,T$ are sets of vertices in a graph $G$, then either …

Let $k\geq 1$ be fixed. Given a digraph $G$ and terminals $s_1,t_1,s_2,t_2,\dots,s_k,t_k$, where each pair $(s_i,t_i)$ specifies a directed path request, consider the problem of fi…

Beineke–Harary conjecture. There are $k+l$ edge-disjoint paths connecting these two vertices, of which $k+1$ are internally disjoint.