18 problems

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…

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

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…

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…

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.

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…

Let $\mathcal{G}$ be a hereditary graph class. A graph class is $(\mathsf{tw},\omega)$-bounded if its treewidth is bounded by a function of its clique number, and it has bounded tr…

An (even hole, diamond)-free graph is a graph containing neither an even hole nor a diamond as an induced subgraph. Its tree independence number is denoted by…