43 problems

Borodin's cyclic coloring conjecture. Every connected plane graph $G$ satisfies

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

Let $G$ be a 2-connected plane graph, and let $\chi_{\mathrm{fo}}(G)$ be the minimum number of colors in a (possibly improper) vertex coloring such that every face is incident with…

$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$ be a plane graph, let $\Delta(G)$ be its maximum degree, and let $\chi_{vef}(G)$ denote the least number of colors in an entire coloring of the vertices, edges, and faces o…

Let $G$ be a plane graph, and let $\chi_{vf}(G)$ denote the least number of colors in a simultaneous proper coloring of the vertices and faces of $G$. Ringel's vertex-face coloring…

Let $G$ be a plane graph, and let $u$ be a positive integer. An $nu$-facial edge-coloring of $G$ is an edge-coloring in which all edges on every facial trail of length at most…

$4_n$ existence and zigzag conjecture. (i) A z-knotted $4_n$ exists if and only if $n\geq 30$ and $n\equiv 2\pmod 4$. (ii) A tight $4_n$ exists if and only if $n\geq 8$ and…

Curvature-graph conjecture. The graph of curvatures of any tight graph of type $3_n$ is the graph in the first of those three cases.

DDF's conjecture. Every z-knotted $3$-valent plane graph has an odd number of edges of type I.

Let $i$ be the number of faces of an irreducible $i$-hedrite, and let a central circuit be a central circuit of the hedrite. An irreducible $i$-hedrite is maximal irreducible when…

Plane spanning tree partition conjecture. Every complete geometric graph on $2n$ vertices can be partitioned into $n$ plane spanning trees.

Aichholzer–Orthaber–Vogtenhuber's conjecture. For each pair of vertices $s,t$ in a simple drawing of $K_n$, there exists a plane Hamiltonian path from $s$ to $t$.

Facial-cycle conjecture. Every non-decomposable critically $k$-frustrated signed plane graph has exactly $2k$ facial cycles, each of which is a negative cycle.

Let $G$ and $\hat{G}$ be a pair of simple, 3-connected plane graphs corresponding to a cellular decomposition of $\mathbb{C}$ and its dual. A circle configuration is a configuratio…

Let $G$ be a plane graph, and let $P$ be a set of non-crossing single-touch shortest paths in $G$. The path covering with forests number of $P$, denoted by $\operatorname{PCFN}(P)$…

Plane-path conjecture. There is an absolute constant $\varepsilon>0$ such that every complete $n$-vertex simple topological graph contains a plane path of length $n^{\varepsilon}$.

Let $(G,\chi)$ be a plane graph, meaning a planar graph equipped with a plane ribbon structure. A sandpile torsor structure assigns a free transitive action of the sandpile group…

Let $G$ be a plane graph, and let $\ell$ be a positive integer. An $\ell$-facial vertex coloring of $G$ is a vertex coloring in which vertices occurring on the same facial walk wit…

Subdivision cyclic coloring conjecture. Every such graph $G$ satisfies

Plummer–Toft conjecture. Every simple $3$-connected plane graph $G$ satisfies

Borodin–Broersma–Glebov–van den Heuvel conjecture. Every plane graph $G$ with $\Delta^*(G)$ and $k^*$ sufficiently large has a cyclic coloring with

Let $G$ be a plane graph, and let $\overline{G}_{vef}$ denote its combined vertex-edge-face graph. The Alon–Tarsi conjecture. Every plane graph $G$ satisfies … If true, this would…

Let $G$ be a plane graph, and let $G_{vf}$ denote its vertex-face graph. The Alon–Tarsi conjecture. Every plane graph $G$ satisfies … This would extend the corresponding list-colou…

Maximum-degree-two conjecture. If $G[X]$ has maximum degree at most $2$, then