406 problems

Every finite planar graph $G$ admits a colouring $c:V(G)\cup E(G)\to\{1,2,3,4\}$ such that: (i) any two adjacent vertices, adjacent edges, or incident vertex-edge pairs receive dis…

For every simple planar graph $G$ with $n=|V(G)|$ vertices, if $a(G)$ denotes the maximum number of vertices in an induced forest of $G$, then $a(G)\geq \frac{n}{2}$.

Wang's conjecture. The D-coloring number of $G$ satisfies

Let $k\geq 3$, and let $h_k(n)$ denote the number of induced copies of $C_{2k+1}$ obtained by evenly blowing up $k$ pairwise non-adjacent vertices in a $C_{2k+1}$ on $n$ vertices.…

A graph $G$ is 3-connected if it remains connected after the deletion of any set of at most two vertices, and it is planar if it can be drawn in the plane without edge crossings. L…

Let $(G,\sigma)$ be a signed planar graph, and let $g_{ij}(G,\sigma)$ denote the corresponding signed girth parameter; let $SPC(k)$ be the signed projective cube of dimension $k$,…

A planar semi-cover of $K_{2,2,2,1}$ is a planar graph $G'$ equipped with the projection structure described in the paper. Suppose $G'$ satisfies the following conditions: if…

Let $ex_{\mathcal{P}}(n,2C_4)$ denote the maximum number of edges in an $n$-vertex planar graph containing no two vertex-disjoint copies of the cycle $C_4$. Planar Turán conjecture…

Let $G$ be an $n$-vertex $C_{\ell}$-free plane graph, meaning that $G$ contains no cycle of length $\ell$, where $\ell\geq 7$. Write $e(G)$ for the number of edges of $G$. Asymptot…

All graphs are finite, simple, undirected graphs. Let $G$ be a graph and let $\sigma:E(G)\to\{-1,+1\}$ be a signature; the pair $(G,\sigma)$ is a signed graph, with underlying grap…

Circular homomorphism conjecture. Every planar graph $G$ of girth at least $4k$ admits a homomorphism to $C_{2k+1}$. Equivalently,

Let $G$ be a vertex-regular planar graph, and suppose that all but two faces of $G$ have the same degree. Nearly platonic graph conjecture. The remaining two faces must have the sa…

Let $G$ be a planar graph and let $k$ be an integer. The $k$-recoloring graph $R_k(G)$ has vertices corresponding to proper $k$-colorings of $G$, with edges joining colorings that…

Polynomial-size grid drawing problem. For every planar graph $G$, there is a proper grid drawing of $G$ in a grid of polynomial size.

K4 subgraph conjecture. Every U$3$LC planar graph has $K_4$ as a subgraph.

Seymour's conjecture. Every planar graph whose odd cycles all have length at least $2k+1$ has a homomorphism to $PQ_{2k}$.

Asymptotic ratio conjecture.

Planar graph Markov width conjecture. There is a universal constant $C$ such that

Let $G$ be a plane graph. A plane graph is generically rigid if its generic realizations are infinitesimally rigid, and it can be straightened as a pseudo-triangulation if its embe…

Let $G$ be a planar graph. For each internal face $F$ in a plane drawing of $G$, let $G_F$ denote the subgraph induced by the vertices incident with $F$. Compact visibility conject…

Let $G$ be a planar bipartite graph, and let $P(G,t)$ be its chromatic polynomial. Let $\tau=(1+\sqrt{5})/2$ be the golden ratio. Salas–Sokal conjecture. … Equivalently, planar bip…

Let $G$ be a loopless planar graph, and let $P(G,t)$ be its chromatic polynomial. Thomassen's conjecture. The real chromatic roots of planar graphs are dense everywhere in … Real c…

Let $G$ be a planar bichromatic graph, meaning a planar graph whose vertices can be coloured with two colours so that adjacent vertices have different colours. Let $a(G)$ denote it…

Let $G$ be a planar graph, and let $a(G)$ denote its algebraic connectivity, the second-smallest eigenvalue of its Laplacian. The graphs $K_4$ and $2K_1\dot{+}C_4$ are the complete…

Let $A$ be a nonsingular alternating matrix, and let $D$ be the matrix-algebra deformation of $\mathbb{C}[\operatorname{coker} A]$ defined by the twisted relations in the paper. Le…