139 problems

Let $T$ be a tree, and consider the equivalence class of $T$ under mutual embeddability, whose elements are counted up to isomorphism. Tree Alternative Conjecture. The number of is…

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

Stahl's conjecture. Every genus polynomial is real-rooted.

Let $H$ be a graph with chromatic number $\ell:=\chi(H)$ and bandwidth measuring that $H$ has not too strong expansion properties. Let $G$ be a graph with minimum degree…

A 2-Platonic graph of type $(k,l)$ is a graph in which all vertex degrees equal $k$ and all face degrees equal $l$, with at most two exceptions among the vertices or faces. Let $G$…

Gupta's conjecture. Planar graphs admit embeddings into $\ell_1$ with bounded distortion. Equivalently, string graphs admit embeddings into $\ell_1$ with bounded distortion.

Let $G_1$ and $G_2$ be graphs embedded on a closed surface $S$, and let the joint crossing number be the minimum number of crossing points between $h(G_1)$ and $G_2$ over all homeo…

Let $G$ be a graph on $n$ vertices. Its separation dimension is the smallest integer $d$ for which there is an embedding $\phi:G\rightarrow\mathbb{R}^{d}$ such that, for every pair…

White's conjecture. Except for finitely many values of $n$, the genus of the complete graph minus a Hamiltonian cycle equals this Euler lower bound:

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 $G$ and $H$ be graphs on $n$ vertices, let $\Delta(H)$ be the maximum degree of $H$, and let $\chi(H)$ be its chromatic number. Bollobás–Komlós conjecture. For the class of non…

Böhme–Saran conjecture. A graph has a linkless embedding if and only if it has a flat embedding.

Classification conjecture. If $\Gamma$ is isometrically embeddable in a half-cube, then $\Gamma$ occurs in Table 3, Table 4, or in one of the infinite series discussed in this sect…

The embeddability conjecture for $(3,5)$-polycycles. Except for $(3^5)$ and $3^5-v$, any $(3,5)$-polycycle is embeddable if and only if it does not contain, as an induced subgraph,…

Let $\Gamma$ be a graph with $r$ interaction sites, and let GOS structures on $\Gamma$ produce surfaces with non-orientable genus. The maximum possible non-orientable genus is $r$.…

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,

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

Cycle double cover conjecture. Every bridgeless graph has a cycle double cover.

The discrete filling-area density conjecture.

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

Let $G$ and $H$ be graphs, and let $\boxempty$ denote the Cartesian product of graphs. A graph is outer-cylindrical (OC) if it has a planar embedding with two vertex-disjoint facia…

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…