724 problems

Let $G$ be a planar graph with maximum degree $\Delta$, and let $\chi_2(G)$ denote the minimum number of colors in a coloring in which vertices at distance at most $2$ receive dist…

A planar graph without cycles of length 4 or 5 is a planar graph containing no cycle of length $4$ or $5$. Steinberg's conjecture. Every planar graph without cycles of length $4$ o…

Barnette's conjecture. Every planar, $3$-connected, cubic bipartite graph is Hamiltonian.

Tait's conjecture. Every $3$-regular, $3$-connected, planar graph is Hamiltonian.

Grünbaum's conjecture. Every planar graph admits an acyclic coloring with $5$ colors.

Albertson–Berman's conjecture.

A triangulated planar graph is a planar graph in which every face, including the outer face under the relevant convention, is a triangle; let $n$ denote its number of vertices and…

Let $G$ be a planar, $4$-edge-connected, $4$-regular simple graph whose size is divisible by $3$. A claw-decomposition is a partition of the edges of $G$ into subgraphs isomorphic…

Thomassen's conjecture. Every such graph $G$ admits a crumby red-blue vertex coloring.

Let $k\geqslant 5$ be an integer. For a graph $G$, write $\chi_2(G)$ for its 2-distance chromatic number, $\Delta(G)$ for its maximum degree, and say that $G$ has girth at least…

Let $G$ be a planar graph with $n$ vertices, let $P(G,k)$ denote its coloring polynomial, and let $k$ be a real number with $k\geq 4$. Birkhoff–Lewis conjecture. For every such gra…

Lai et al.'s conjecture.

Let $G$ be a planar graph on $n$ vertices, let $\lambda(G)$ denote the spectral radius of its adjacency matrix, let $P_{n-2}$ be the path on $n-2$ vertices, and let $\vee$ denote g…

A planar graph is a graph that can be drawn in the plane without crossings. A graph is 4-choosable if every assignment of lists of four colors admits a proper coloring from those l…

In a graph drawing, a simple drawing is one in which both adjacent edges and non-adjacent edges satisfy the relevant simplicity conditions; a plane Hamiltonian cycle is a cycle tha…

Let $G$ be a planar graph of order $n\geq 9$, let $\rho(G)$ denote its spectral radius, let $K_2$ be the complete graph on two vertices, let $P_{n-2}$ be the path on $n-2$ vertices…

Harborth's conjecture. The maximum number of edges of a matchstick graph on $n$ vertices is

Let $G$ be an $n$-vertex 4-connected planar triangulation, meaning a planar triangulation that remains connected after the removal of fewer than four vertices. A Hamiltonian cycle…

Induced maximal outerplane subgraph conjecture.

A planar graph is a graph embeddable in the plane, and its combinatorial curvature is the angle-deficiency curvature determined by an embedding in a surface. Higuchi's conjecture.…

Let $C_{2k}$ be an even cycle of length $2k$, and let $n$ be the number of vertices of a planar graph. Cox–Martin conjecture. The maximum number of copies of $C_{2k}$ in an $n$-ver…

Let $G$ be a planar graph containing an arbitrarily large number of triangles, with the triangles sufficiently far apart. Havel's conjecture. Such a graph may be $3$-colorable. Hav…

Let $G$ be a graph, and let $P_G(q)$ denote its chromatic polynomial, whose roots are called chromatic roots. The Beraha numbers are the numbers … A planar triangulation is a plana…

Dross–Montassier–Pinlou conjecture. Every planar graph $G$ of girth at least $g$ satisfies

Gartland–Lokshtanov's conjecture. For every planar graph $H$, graphs that are $H$-induced-minor-free admit balanced separators consisting of few neighborhoods.