17 problems

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…

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

Gartland–Lokshtanov's conjecture. For every planar graph $H$ there exists an integer $k_H$ such that every $H$-induced-minor-free graph $G$ has a balanced separator dominated by at…

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

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…

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

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…

A string graph is the intersection graph of a collection of curves in the plane. A separator in a graph $G=(V,E)$ is a subset $S\subseteq V$ such that no connected component of…

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…

Let $P$ be a simple $d$-polytope with $m$ vertices, and let $G_P$ be its graph. Kalai's separator conjecture. There exists a subset $V'$ of vertices of $P$ such that … and removing…