23 problems

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 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 $d$ be a positive integer and let $\mathcal{G}$ be a hereditary $K_{1,d}$-free graph class. Dallard et al.'s conjecture. The class $\mathcal{G}$ has bounded tree-independence n…

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…

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…

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

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…

Polylogarithmic tree-independence conjecture. For every positive integer $t$, there is an integer $d=d(t)$ such that for every $n\ge2$, every $n$-vertex graph with no induced minor…

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…

For a graph $H$, $kH$ denotes the disjoint union of $k$ copies of $H$, and a graph is $H$-induced-minor-free if it does not contain $H$ as an induced minor. The planar induced-mino…

$K_6$ minor conjecture. If $G$ contains $K_6$ as a minor, then $G$ contains a triangle as a subgraph or $G$ contains $K_{3,3}$ as an induced minor.

Odd signable graph conjecture. If $G$ is an odd signable graph (in particular, if $G$ is an even-hole-free graph), then $G$ does not contain $K_{3,3}$ as an induced minor.

The induced-grid conjecture. The class $\mathcal{C}$ has bounded tree-independence number if and only if $\widehat{\mathcal{C}}$ does not contain all planar graphs. This is propose…