71 problems

Erdős–Rényi face conjecture. The expected number of faces is

Odd-cycle naive-dimension conjecture. The cyclic interval lemma holds for every odd $m$; consequently,

Random embedding edge-type conjecture. The expected numbers of bad singular edges, good singular edges, and regular edges are respectively

For a fixed graph $H$ with $h\ge 3$ edges and no isolated vertices, determine whether every sufficiently large $n$-vertex graph $G$ satisfying the relevant minimum-degree hypothesi…

Burr's conjecture. Every oriented tree of order $n$ is $(2n-2)$-universal.

Loebl–Komlós–Sós conjecture. If at least $n/2$ vertices of $G$ have degree at least $d$, then $G$ contains a copy of $T$.

Bounded-distance crossings conjecture. There is an integer $k$ such that for every pair of crossing edges $uv,xy$ in $G$, we have

Let $S$ be a surface, let $n_S$ be the largest order of a complete graph that embeds into $S$, and let $\gamma(G,\sigma)$ and $\gamma^*(G,\sigma)$ denote the relevant orientable an…

Let $\Gamma$ be a $2$-connected graph. A strong embedding is an embedding of a graph in a surface in which every facial walk is simple. Jaeger's strong embedding conjecture. Every…

For each graph family listed in Example, let its genus polynomial be the polynomial whose coefficients count embeddings by genus. Stahl's conjecture. The zeros of the genus polynom…

Strong embedding conjecture. Every $2$-connected graph has a strong embedding on a surface.

Cyclic interval conjecture. The displayed inequality holds for every odd $m$ and every nonempty proper subset $x\subseteq\mathbb{Z}_m$; consequently,

Let $G$ be a graph, and let $g_k(G)$ denote the number of equivalence classes of 2-cell embeddings of $G$ on the orientable surface of genus $k$. The sequence…

The discrete filling-area density conjecture.

Oriented strong embedding conjecture. Every $2$-connected graph has a strong embedding on some orientable surface.

Let $H$ be a graph with a self-gluing $d711: U_1 \to U_2$, and let $K$ be a valid minimal cut for this self-gluing. Construct the swapping $(H',\psi)=\operatorname{Sw}(H,d711,K)$ b…

Bollobás--Eldridge--Catlin conjecture. If

Let $E \subseteq \mathbb{F}_q^d$ and let $R \subseteq \mathbb{F}_q \setminus \{0\}$. Let $C$ be the constant appearing in Theorem, whose conclusion guarantees the existence of the…

Let $K_n$ be the complete graph, let $S_t$ be the orientable surface of genus $t$, and let $\delta_t(K_n)$ and $\mu_t(K_n)$ denote its Euler excess and skewness, respectively. Guy'…

Cluster-size conjecture. Theorem remains valid for $H$ with clusters of size at most

Let $\Sigma$ be a connected compact surface without boundary and let $g$ be its Euler genus. A finite $\Sigma$-cover is a finite cover of a connected graph that embeds in $\Sigma$.…

Let $\Sigma$ be an orientable surface of Euler genus $g$, and let a finite $\Sigma$-cover mean a finite cover of a connected graph that embeds in $\Sigma$. Orientable higher-genus…

Let $\Sigma$ be a connected compact non-orientable surface without boundary. A finite $\Sigma$-cover is a finite cover of a connected graph that embeds in $\Sigma$. Hliněný's conje…

Let $d\geq 3$, and let $Y$ be a locally finite, non-planar, transitive graph with separation profile $\simeq n^\alpha$ for some $\alpha \in (0,1]$. A $1$-thick embedding of a graph…

Realization conjecture. For any integers $n_1,n_2,n_3,n_4$ whose sum is odd, there exists an almost embedding $f:K_4\to\mathbb R^2$ such that