10 problems

Induced Menger conjecture. If a graph admits no $k$ pairwise non-adjacent paths between $u$ and $v$, then it admits a set of $f(k)$ neighborhoods disconnecting $u$ from $v$, for so…

Let $\Gamma$ be a web, and let $A$ and $B$ be its distinguished vertex sets. An $A$--$B$-separating set $S$ meets every $A$--$B$ path; $S$ is linkable into $A$ in…

Let $G$ be a graph and let $X,Y\subseteq V(G)$. An $X$-$Y$ path is a path with at least one end in $X$ and at least one end in $Y$. A set is $(a,b)$-centered if it is contained in…

Let $\Sigma$ be a fixed surface. Let $G$ be a graph embeddable in $\Sigma$, and let $X,Y\subseteq V(G)$. An $X$-$Y$ path is a path with at least one end in $X$ and at least one end…

Let $G$ be a finite or infinite graph, and let $X,Y\subseteq V(G)$. An $X$-$Y$ path is a path with at least one end in $X$ and at least one end in $Y$. A set $Z\subseteq V(G)$ is…

Let $G$ be a finite or infinite graph, and let $X,Y\subseteq V(G)$. An $X$-$Y$ path is a path with at least one end in $X$ and at least one end in $Y$. For sets $S,T\subseteq V(G)$…

Let $K,n,m,r\in\mathbb{N}$. A graph is $(M,A)$-quasi-isometric to a graph of tree-width at most $g$ in the usual coarse sense, and connected sets are at least $K$ apart when every…

Let $G$ be a graph, let $\Delta(G)$ denote its maximum degree, and let $X,Y\subseteq V(G)$. A set of vertices separates $X$ and $Y$ if it intersects every $X$-$Y$-path; paths are p…

MM3 NP-completeness conjecture. The decision problem MM3 is NP-complete.

Let $G$ be an infinite graph, and let $A$ and $B$ be vertex sets. A set of paths between $A$ and $B$ and a vertex set separating $A$ from $B$ form a structural Menger pair when the…