212 problems

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…

A topological graph is a graph drawn in the plane with vertices represented by points and edges by simple Jordan arcs; it is $k$-quasi-planar if it contains no $k$ pairwise crossin…

Schröder's conjecture. The cop number of a genus-$g$ graph satisfies

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…

Let $G$ be a graph. A linkless embedding of $G$ in $\mathbb{R}^3$ is an embedding in which no two disjoint cycles are linked, and a linear linkless embedding is such an embedding i…

Let $S$ be a two-dimensional manifold, let $T$ be a triangulation of $S$, and let $G$ be the dual graph of $T$. Grünbaum's surface-coloring conjecture. The graph $G$ is $3$-edge-co…

Let $G$ be a graph embeddable on an orientable surface of genus $g$, and let $c(G)$ denote its cop-number, the minimum number of cops required to capture a robber on $G$. Schroeder…

Let $G$ be a bridgeless graph, and let a cycle double cover be a family $\mathcal{F}$ of cycles of $G$ such that each edge of $G$ is contained in exactly two members of…

For a simple drawing of $K_n$, let $\triangle(n)$ denote the minimum number of empty triangles among all such drawings. An empty triangle is a triangle induced by three vertices su…

A 2-manifold is a graph in which every unit sphere is a cyclic graph with at least 4 vertices. Albertson–Stromquist conjecture. Every 2-manifold has chromatic number at most $5$. T…

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

For each nonnegative integer $g\neq 2$, let … and let $S_g$ denote the orientable surface of genus $g$. A Kainen drawing is a drawing attaining Kainen's lower bound for the surface…

$2n-3$-edge conjecture. Every simple drawing of $K_n$ with $n\geq 3$ contains a plane Hamiltonian subdrawing on $2n-3$ edges.

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…

Grünbaum–Nash-Williams conjecture. Every 4-connected map on the torus is Hamiltonian.

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…

Andreae–Schroeder conjecture. One has

The flow polynomial and the golden identity are considered for cubic graphs; the golden identity is the flow-polynomial analogue of the corresponding identity for the chromatic pol…

A genus polynomial is the polynomial whose coefficients record the genus distribution of a graph. Stahl's conjecture. Every genus polynomial is real-rooted. This conjecture was dis…

Let $G$ be a $2$-connected graph, and let $\Gamma$ be a non-trivial spatial graph of $G$. Define the representativity of $\Gamma$ by … where $\mathcal{F}$ is the set of all closed…

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…

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…