21 problems

Let $\mathcal{G}$ be a hereditary class of graphs. A class has bounded tree-independence number if there is a constant $c\in\mathbb{N}$ such that every graph in the class admits a…

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…

Let $d\geq 2$, and let $\mathcal{G}$ be a $K_{1,d}$-free graph class of twin-width at most $3$. Twin-width conjecture. Does $\mathcal{G}$ have bounded tree-independence number? The…

Let $d\geq 2$, and let $\mathcal{G}$ be a $K_{1,d}$-free graph class. Sim-width conjecture. If $\mathcal{G}$ has bounded sim-width, then $\mathcal{G}$ has bounded tree-independence…

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…

For $a,b\in\mathbb{N}$, let $K_{a,a}$ be the complete bipartite graph with $a$ vertices in each part, and let the $b$-vertex path be the path with $b$ vertices. Dallard–Krnc–Kwon–M…

Let $\mathcal{F}$ be a finite class of graphs, and let $\mathcal{F}$-free mean having no induced subgraph isomorphic to a member of $\mathcal{F}$. A multiclaw is a graph each compo…

Let $\mathcal{F}$ be a finite class of graphs. A graph is $\mathcal{F}$-free if it has no induced subgraph isomorphic to any member of $\mathcal{F}$. The class of all $\mathcal{F}$…

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

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…

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…

Bounded tree-independence conjecture. For any two positive integers $k$ and $t$, the class of $\{P_k,K_{t,t}\}$-free graphs has bounded tree-independence number.

Dallard–Krnc–Kwon–Milanič–Munaro–Štorgel–Wiederrecht alpha-treewidth Grid conjecture. Replacing treewidth by alpha-treewidth should yield a meaningful induced analogue of the Grid…

A theta is a graph consisting of two non-adjacent ends joined by three pairwise internally disjoint paths of length at least two whose interiors are pairwise anticomplete. A prism…

Tree-independence conjecture. For any two integers $k,t\in\mathbb{N}$ there exists an integer $r$ such that every graph with induced matching treewidth at most $k$ and no induced s…

For positive integers $d$ and $s$, a graph is $\{K_{2,d},P_s\}$-free if it has no induced subgraph isomorphic to $K_{2,d}$ or the $s$-vertex path $P_s$. The $K_{2,d}$-and-path conj…

Let $d$ be a positive integer and let $\mathcal{C}$ be a hereditary graph class excluding $K_{1,d}$. A subdivision of the elementary $k$-wall is obtained by subdividing edges of th…

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…

For positive integers $d$ and $s$, a graph is $\{K_{d,d},P_s\}$-free if it has no induced subgraph isomorphic to $K_{d,d}$ or the $s$-vertex path $P_s$. The biclique-and-path conje…

Tree-independence conjecture. $\mathcal{G}$ is $(\mathrm{tw},\omega)$-bounded if and only if $\mathcal{G}$ has bounded tree-independence number.