22 problems

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;…

Bonnet–Geniet–Kim–Thomassé–Watrigant's conjecture. Every small hereditary graph class has bounded twin-width.

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

Converse of the bounded twin-width smallness theorem. Every small hereditary graph class should have bounded twin-width.

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…

A small graph class is a graph class satisfying the notion of smallness used in the source. Small conjecture. For every small graph class $\mathcal{C}$, there exists…

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 $2$. Bounded clique-width conjecture. Then $\mathcal{C}$ has bounded clique-width. This unrestricted version is false,…

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 $\operatorname{\mathfrak{S}}_{\mathbb{Z}}^f$ be the group of finitely supported permutations of $\mathbb{Z}$, let $T=\{x\mapsto x+c\mid c\in\mathbb{Z}\}$ be the translation gro…

Let $\Gamma$ be a group. Uniform twin-width strengthens twin-width by requiring a uniform bound on the widths of the permutations induced by all elements of $\Gamma$ in a suitable…

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…

Smallness converse. Every small hereditary class of graphs has bounded twin-width.

Let $\mathscr C$ be a hereditary class of binary structures. Call $\mathscr C$ small if the number of its $n$-element structures, bijectively labeled by $[n]$, is at most $n!c^n$ f…

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.