25 problems

Fox–Pach separator conjecture. Every string graph with $m$ edges has a separator of order

Gartland–Lokshtanov's conjecture. For every planar graph $H$, graphs that are $H$-induced-minor-free admit balanced separators consisting of few neighborhoods.

Let $d\ge 2$ be fixed. A separator of a graph on $n$ vertices is a partition of its vertex set into sets $A,B,C$ with $cn\le |A|\le |B|\le (1-c)n$, for a fixed constant $c$ satisfy…

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…

Fixed-radius coarse separator strengthening. For every $k,r\in\mathbb{N}$, there exists $k'\in\mathbb{N}$ such that if $G$ admits $(k,r)$-balanced separators, then $G$ admits a…

A graph class is fractionally tree-alpha-fragile if it has the fractional $\mathsf{tree}\textnormal{-}\alpha$-fragility property; independence degeneracy is the graph parameter def…

Abrishami–Czyżewska–Kluk–Pilipczuk–Pilipczuk–Rzążewski's conjecture. Every graph class with balanced separators consisting of few neighborhoods admits tree-decompositions whose bag…

Abrishami–Czyżewska–Kluk–Pilipczuk–Pilipczuk–Rzążewski's conjecture. For every $k,r\in\mathbb{N}$, there exist $k',r'\in\mathbb{N}$ such that if $G$ admits $(k,r)$-balanced separat…

Cliquewidth preservation conjecture. There is a function $f$ such that every graph in $\mathcal C$ has cliquewidth at most $f(a)$.

Abrishami et al.'s conjecture. The existence of weighted balanced separators contained in a bounded number of balls of bounded radius implies the existence of a tree-decomposition…

Induced Grid Minor Conjecture. There exists a function $f$ such that for every planar graph $H$, every $H$-induced-minor-free graph $G$ has a balanced separator dominated by $f(H)$…

Let $t,d greater than or equal to 1$ be integers, and let $G$ be an $n$-vertex graph in the class $SphereInt{d}t$ of sphere intersection graphs. A balanced separator is a vertex se…

Gartland's conjecture. For every positive integer $t$, there is an integer $d=d(t)$ such that every $\mathcal{L}_t$-free graph $G$ with no induced subgraph isomorphic to a subdivis…

Let $\mathcal{G}$ be an arbitrary $(\operatorname{tw},\operatorname{had})$-bounded graph class, meaning that there is a function $f$ with…

Let $n\geq 14$. A 3-connected planar quadrangulation is a 3-connected planar graph in which every face is bounded by a cycle of length four. Let $\mathcal{G}^\ast$ be the class con…

Dvořák's conjecture. Every hereditary class of graphs with sublinear separators is fractionally treewidth-fragile.

Infinite-graph extension conjecture. The local 2-separator theorem is true for infinite graphs.

Let $G$ be a graph and let $p$ be a polynomial such that the expansion of $G$ is bounded by $p$. A cost assignment is a function … For integers $t\geq 1$ and $q\geq 0$, a set…

Let $G$ be a graph and let $x$ and $y$ be distinct vertices of $G$. Write $\overset{{}_{\;\rightarrow}}{S}(G-xy)$ for the partially ordered set of oriented vertex separators of…

Let $G$ be a graph from a class with polynomial $\omega$-expansion, let $q$ be the vertex-cost function, and let $\ell$ be the parameter in the separator theorem. A set $C\cup M$ i…

Clique-separator conjecture. There is a clique cover $C$ in $G$ such that removing

Separation conjecture. The class of all graphs $G$ for which $\hat\beta_t(G)$ is polynomially bounded by $t$ has a suitable separation theorem with respect to the measure $\alpha$:…

Let ${\cal G}$ be a subgraph-closed class of graphs. Suppose that ${\cal G}$ has strongly sublinear separators. Subexponential expansion conjecture. The expansion of ${\cal G}$ is…

Let $H$ be a fixed graph, and let an $H$-free graph be a graph with no induced subgraph isomorphic to $H$. A CS-separator is a family of cuts separating every disjoint clique from…

Let $G$ be a graph on $n$ vertices. A clique–stable set separator is a family of cuts such that every disjoint clique and stable set of $G$ are separated by one of the cuts. Clique…