17 problems

Erdős–Hajnal conjecture. Every proper hereditary class of graphs has the Erdős–Hajnal property.

Implicit graph conjecture. Every hereditary class of graphs containing at most $2^{O(n\log n)}$ graphs with $n$ vertices has an induced-universal graph of polynomial size.

Let $G$ be a $2$-connected graph. For the forbidden linear ordering family consisting of $(G,\le)$, consider the problem of deciding, for an input graph $H$, whether there is an…

Let $\mathcal C$ be a hereditary class of finite structures, and let $\tilde{\mathcal C}_{\leq \omega}$ be the class of countable structures whose age is included in $\mathcal C$.…

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

Let $\mathcal{C}$ be a hereditary class of finite graphs. The bounded clique-width conjecture. If $\mathcal{C}$ is $2$-well-quasi-ordered, then $\mathcal{C}$ has bounded clique-wid…

Let $\mu$ be a finite relational signature, and let $\mathscr S_{\mu}$ be the class of all relational structures of signature $\mu$ without any finite monomorphic decomposition. A…

For a graph $G$, let $h(G)$ be the largest integer $kgeq 0$ such that $G$ has $k$ vertices of degree at least $k$. The universal $h$-index characterization conjecture. The characte…

A hereditary class is a class of finite graphs closed under taking induced subgraphs, and a class is well-quasi-ordered if it has no infinite descending chain or infinite antichain…

Let $\mathcal C$ be an age of finite structures, ordered by embeddability, and let $[\omega]^{<\omega}$ denote the collection of finite subsets of $\omega$, ordered by inclusion. A…

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

Implicit graph conjecture. Every factorial hereditary class has an $O(\log n)$-bits adjacency labeling scheme.

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

A hereditary graph property $X$ is a class of graphs closed under taking induced subgraphs. A graph property is factorial when the number of labelled graphs in the property on $n$…

A hereditary graph class is a class closed under taking induced subgraphs, and an implicit representation assigns each vertex a binary code of length $O(\log n)$ from which adjacen…

Finite basis conjecture. There is a finite subset $\mathfrak A$ of pairwise incomparable structures in $\mathscr S_{\mu}$ such that every member of $\mathscr S_{\mu}$ embeds some m…

Let $\mathfrak D$ be a hereditary class of indecomposable ordered binary structures. Suppose that $\mathfrak D$ is hereditary well-quasi-ordered and hereditary algebraic. Sum-closu…