14 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 $\mathscr C$ be a hereditary weakly sparse class of graphs. An internal tree-ordering expansion of a graph is an expansion by the forest-ordering defined by a spanning forest;…

Let $\mathcal{C}$ be a hereditary class of graphs. FO model-checking conjecture. There is an FPT first-order model-checking algorithm for graphs in $\mathcal{C}$ if and only if…

Twin-width gap conjecture. The twin-width of $G$ is asymptotically larger than $\operatorname{lb}_1(G)$, that is,

A hereditary class is a graph class closed under induced subgraphs, and twin-width is the graph parameter measuring the minimum contraction complexity under sequences of vertex ide…

For a tournament $T$ and an ordering $\prec$ of $V(T)$, let $T^{\prec}$ be its backedge graph. A BST-ordering is the ordering associated with a binary search tree satisfying the to…

Let $k\geq 1$. A tournament has twin-width at most $k$ if its twin-width is at most $k$. The bounded twin-width conjecture. The class of tournaments with twin-width at most $k$ is…

Let $\mathcal{C}$ be a stable class of graphs of twin-width at most $2$. Stable twin-width 2 conjecture. Then $\mathcal{C}$ has bounded clique-width. This conjecture is the correct…

Let $\mathcal{C}$ be a class of graphs of twin-width at most $3$, and suppose there exists an integer $t$ such that no graph $G\in\mathcal{C}$ contains $K_{t,t}$ as a subgraph. Spa…

Let $\mathcal{Q}$ be the graph class defined in the preceding construction. A graph class is small if there is a constant $c$ such that the number of its labelled $n$-vertex graphs…

Let $\mathcal{C}$ be a class of graphs closed under induced subgraphs. Call $\mathcal{C}$ small if there is a constant $c$ such that, for every $n$, it contains at most $n!\,c^n$ g…

Finitely generated groups conjecture. For every group $\Gamma$ generated by a finite set $S$, the class $F(\Gamma,S)$ has bounded twin-width.

Optimal labeling conjecture. Every bounded twin-width class has a $(1+o(1))\log n$-bits labeling scheme.

Small conjecture. Every small hereditary class has bounded twin-width.