126 problems

Let $K_{m,n}$ be the complete bipartite graph with part sizes $m$ and $n$, and define … Here $\operatorname{cr}(G)$ denotes the minimum number of crossings in a plane drawing of a…

Let $K_n$ be the complete graph on $n$ vertices, and define … Here $\operatorname{cr}(G)$ denotes the minimum number of crossings in a plane drawing of a graph $G$. Harary–Hill con…

…

For every integer $n\ge 4$ and every rotation system $R$ on an $n$-element set, at least…

Determine, up to isomorphism, all finite simple triangle-free intrinsically knotted graphs $G$ satisfying $|E(G)|=22$.

Let $G$ be a $2$-edge-connected graph embedded in the torus. Robertson's conjecture. If the representativity of the embedding is at least $3$, then $G$ has a nowhere-zero $4$-flow.…

Let $G$ be a connected finite simple graph. A finite planar cover of $G$ is a finite graph that covers $G$ in the graph-theoretic sense, with the covering graph planar. Negami's Pl…

Schröder's conjecture. For every $g\in\mathbb{N}$, we have

3-extendability conjecture. Every $8$-regular optimal $1$-embedded graph $G$ on the Klein bottle is $3$-extendable.

Let $X$ be a geodesic surface of genus $g$, and let $c(X)$ denote its cop number. Schroeder's genus conjecture. … The paper compares this conjecture with a linear upper bound and a…

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…

Vertex-minimality conjecture. For every surface $\Sigma$, the maximum excess is attained by some vertex-minimal triangulation of $\Sigma$ that contains $K_\omega$ as a subgraph. Mo…

Let $\mathbb{P}_4$ be the prefix-reversal graph on the permutations of $\{1,2,3,4\}$, and let $\gamma(\mathbb{P}_4)$ denote its orientable genus. A graph is a pretzel graph if it a…

Nonexistence conjecture for the displayed cover. For every finite planar cover

Conjecture on nonseparating cycle types. If $g \geq 3$ is odd, every triangulation of $N_g$ has a nonseparating cycle that is one-sided and orientable-leaving, one that is one-side…

Nonorientable analogue of Thomassen's conjecture. Every such triangulation contains an NSC such that the two surfaces separated by the NSC have Euler genera $h$ and $g-h$, respecti…

Let ${\cal M}$ be a map, and denote the Euler characteristics of ${\cal M}$, $phial({\cal M})$, and $skew({\cal M})$ by $\chi({\cal M})$, $\chi_p({\cal M})$, and $\chi_s({\cal M})$…

Let $M(G)$ be a connected simple cubic map of girth $4$ embedded in a genus-realizing orientable surface, and suppose all its belts have lengths $\ell$ with $\ell\equiv 0\pmod 4$.…

Let $g>0$. A simple tiling $\mathcal T$ of a genus-$g$ surface has an associated incidence theorem over a division ring ${\mathrm D}$, and $n$ denotes the dimension of the ambient…

Let $\mathcal T$ be a simple tiling of a surface of positive genus, meaning that its underlying graph is $(n+1)$-degenerate, and let ${\mathrm D}$ be a division ring. The incidence…

A separating non-contractible cycle (SNCC) is a cycle in a triangulation that is separating and non-contractible. Let $t$ be a triangulation and let $C$ be an SNCC of $t$ of shorte…

Fix $\theta\in(0,1/2)$ and a sequence $(g_n)$ such that $g_n/n\rightarrow\theta$. Let $\mathbf{T}_{2n,g_n}$ be a uniform triangulation of genus $g_n$ with $2n$ faces. A simple sepa…

A simple separating non-contractible cycle (SNCC) is a simple cycle in a triangulation that is both separating and non-contractible. Let $t$ be an arbitrary triangulation without l…

Let $\Sigma$ be a surface with Euler genus $g$, and let $G$ be a string graph in $\Sigma$. A string representation $\mathcal{C}$ of $G$ in $\Sigma$ assigns a non-self-intersecting…