29 problems

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

Induced-minor characterization conjecture. For every integer $t$ there exist integers $c,d$ such that every graph $G$ either contains $K_{t,t}$ or $\boxplus_t$ as an induced minor…

Let $t$ be a positive integer. For a graph $G$, write $\operatorname{tree-\alpha}(G)$ for its tree-independence number, and let $K_{t,t}$ denote the complete bipartite graph with…

Polynomial-separator or bounded-hole conjecture. There exists a polynomial $p$ and an integer $k$ such that if $G$ has no clique cutset and does not contain $K_{2,3}$ as an induced…

Gartland's conjecture. For every planar graph $H$, MIS admits a polynomial-time algorithm on $H$-induced-minor-free graphs.

Gartland and Lokshtanov's conjecture. For every fixed $r$ and CMSO$_2$ formula $\psi$, $(\operatorname{tw} \leq r,\psi)$-MWIS and $\operatorname{lcol}(3)$ can be solved in polynomi…

Let $d\geq 2$ be an integer, let $G$ be a $K_{1,d}$-free graph, and let $f$ be a polynomial. Polynomial-bound conjecture. There is a polynomial $f$ such that, whenever $G$ does not…

Let $W_{t\times t}$ be the $t$-by-$t$ hexagonal grid and let $K_{t,t}$ be the complete bipartite graph with both sides of the bipartition of size $t$. For a positive integer $t$, l…

For a graph $F$, a graph class excludes $F$ as an induced minor when none of its graphs contains $F$ as an induced minor. A graph class has finite asymptotic dimension when its asy…

Double-wheel conjecture. There exists a function $f:\mathbb{N}^2\rightarrow\mathbb{N}$ such that every $K_{1,d}$-free graph $G$ with…

The induced Grid Theorem. There exists a function $f:\mathbb{N}^2\rightarrow\mathbb{N}$ such that every $K_{1,d}$-free graph $G$ with $\alpha$-$\mathsf{tw}(G)\geq f(k,d)$ contains…

Let $n\in\mathbb{N}$. An induced $(n\times n)$-grid minor is the indicated induced-minor model, and $(M,A)$-quasi-isometry and tree-width have their usual meanings. Then there exis…

Lokshtanov–McCarty's conjecture. There exists a graph $H'$ such that every $H$-induced-minor-free graph with maximum degree at most $\Delta$ is a region intersection graph over an…

Induced-minor-free product structure conjecture. There is a function $f\colon \mathbb{N}\to\mathbb{N}$ such that every $H$-induced-minor-free graph $G$ with maximum degree at most…

Trotignon's conjecture. For all $r,t\in\mathbb{N}$, there exists $c=c(r,t)\in\mathbb{N}$ such that for every graph $G$, if $G$ does not contain $W_{t \times t}$ or $K_{t,t}$ as an…

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

Planar induced-minor conjecture. For every positive integer $t$ and every planar graph $H$, there exists an integer $N_{t,H}$ such that every $K_{1,t}$-free $H$-induced-minor-free…

Georgakopoulos's coarse grid minor conjecture. For every planar graph $H$, there exist $k,q\in\mathbb{N}$ such that every $H$-induced-minor-free graph is $q$-quasi-isometric to a g…

Gartland–Lokastov's conjecture. For every planar graph $H$, there exists $k\in\mathbb{N}$ such that every $H$-induced-minor-free graph $G$ admits a $(k,1)$-balanced separator.

A hereditary class is a graph class closed under induced subgraphs. A string graph is an intersection graph of curves in the plane, and $K_{\ell,\ell}$ is the complete bipartite gr…

Structural conjecture. The class of $3$-connected binary matroids that do not contain $M(K_4)$ as an induced minor is exactly the class of matroids that can be obtained by starting…

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

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

Let a graph class be $(\operatorname{\mathsf{tw}},\omega)$-bounded if its treewidth is bounded by a function of its clique number, and let a hereditary class of graphs have bounded…

A graph class is hereditary if it is closed under taking induced subgraphs. The tree-independence number of a graph is the minimum, over its tree-decompositions, of the largest ind…