71 problems

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…

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.

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

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…

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

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

Spanning triangulated subsurface conjecture. For all $g \geq 0$, every triangulation of a surface of Euler genus $g$ contains a spanning subgraph which is a triangulated…

Let $\delta_1(c)$ denote the minimum genus of a dual-separable embedding of a $c$-connected graph, and let $\gamma(K_{c+1})$ denote the genus of the complete graph $K_{c+1}$. Optim…

Klimošová–Piguet–Rozhoň local degree conjecture. If

Klimošová–Piguet–Rohzoň conjecture. If at least $rn$ vertices of $G$ have degree at least $d$, then $G$ contains a copy of every $r$-skew tree with $d$ edges.

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$.

Let $G$ be a graph that triangulates some surface, and let its genus distribution be the sequence of numbers of $2$-cell embeddings of $G$ in orientable surfaces of each genus. Sur…