16 problems

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.

Tallgren's conjecture. The only trees $T$ for which $\mathcal G_{\{T\}}$ has a universal object are the paths and the trees obtained from a path by attaching one additional edge.

Single-constraint conjecture.

Kojman's conjecture. Closure of the constraint class $\mathcal C$ under homomorphic image should be a key condition for the existence of a universal countable $\mathcal C$-free gra…

Let $C$ be a finite connected graph whose underlying tree $\tilde C$ is neither a path nor a near-path, and suppose there is a weakly or strongly universal $C$-free graph. Then the…

Let $C$ be a finite or countable graph with no isolated vertices, and decompose it into blocks, its 2-connected components. Let $\tilde C$ be the underlying tree of $C$: its vertic…

Let $C$ be a finite or countable graph with no isolated vertices. Decompose $C$ into its blocks, where each block is a 2-connected component, and let $\tilde C$ be the underlying f…

Let $s(n)$ denote the minimum number of vertices in a universal graph for all trees with $n$ vertices. Asymptotic-limit conjecture. The limit … exists. Determining this limit would…

For each $n$, let $\mathscr{P}_n$ denote the family of planar graphs on $n$ vertices, and let $\mathscr{U}(\mathscr{P}_n)$ be its induced-universal graph. The trivial lower bound f…

For $D,n \in \mathbb{N}$ and $d \in \mathbb{Q}$, let $\mathcal{H}_d^D(n)$ be the family of graphs in $\mathcal{H}_d(n)$ with maximum degree $D$. Bounded-degree bounded-density univ…

For $d \in \mathbb{Q}$ and $n \in \mathbb{N}$, let $\mathcal{H}_d(n)$ be the family of all graphs with $n$ vertices and density at most $d$, where the density of a graph $H$ is … A…

Universality conjecture. The following are equivalent:

Quadratic universal graph conjecture. The minimum number of vertices in a bipartite permutation graph containing all $n$-vertex bipartite permutation graphs is

Universal bounded-degree graph conjecture. Let $\Delta\in\mathbb N$ and $p=\omega\left(n^{-1}\log^{1/\Delta}n\right)^{\frac{2}{\Delta+1}}$. Then, with high probability, $G_{n,p}$ i…

Let $\mathcal{F}$ be a class of graphs, let $\lambda_{\mathcal{F}}(k)$ denote the least order of a $k$-universal graph for $\mathcal{F}$, and let $D(\mathcal{F})$ be the exponent a…

Solidity and Pathlike conjectures. The following two claims are conjectured: