410 problems

Every planar graph $G$ contains a vertex subset $S\subseteq V(G)$ such that the induced subgraph $G[S]$ is a forest and $|S|\geq \frac{|V(G)|}{2}$.

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}$.

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…

Tile the unit square by, possibly infinitely many, squares of varying sizes, with at most three squares meeting at any corner. Color each square black or white independently, each…

Let $G$ be a planar graph, and let $\fva(G)$ denote its fractional vertex-arboricity. Fractional Albertson–Berman conjecture. Every planar graph has fractional vertex-arboricity at…

Let $G$ be a graph given by $n$ points in $\mathbb{R}^2$, where any two distinct points are at least distance $1$ apart, and we draw an edge between two points if they are distance…

Call a planar graph on $v$ vertices saturated if it has $3v-6$ edges. Must every graph on $n$ vertices with $⌊n^2/4⌋+⌊(n+1)/2⌋$ edges contain a saturated planar subgraph on more th…

For every $ε>0$, is there a constant $c_ε$ such that every $n$-vertex graph with $⌊n^{1+ε}⌋$ edges contains a nonplanar subgraph on at most $c_ε$ vertices?

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…

Let $G$ be a planar graph. An odd coloring of $G$ is a proper vertex coloring such that every non-isolated vertex has a color appearing an odd number of times in its neighborhood;…

Albertson–Berman's conjecture.

A planar graph is a graph that can be embedded in the plane. Steinberg's conjecture. Every planar graph with no cycles of length four or five is $3$-colorable. Steinberg's conjectu…

Heckman–Thomas planar conjecture. Every subcubic triangle-free planar graph is fractionally $8/3$-colorable.

Dunbar et al.'s conjecture. If $G$ is a planar graph, then

Let $n$ be the number of vertices, let $P_{n-1}$ be the path on $n-1$ vertices, and let $\vee$ denote the join of graphs. Cvetković–Rowlinson's conjecture. The outerplanar graph on…

Let $G$ be a planar graph of girth at least $k$, and let $\Delta$ be its maximum degree. Wang–Lih conjecture. For every $k\ge 5$, there exists $\Delta_k$ such that, if…

Neumann–Lara's conjecture. Every orientation of a planar graph has dichromatic number at most $2$.

Let $G$ be an $n$-vertex triangle-free planar graph. A proper 3-coloring of $G$ is a vertex coloring with three colors in which adjacent vertices receive different colors. Thomasse…

Let $G$ be a $3$-regular, $3$-connected planar graph. Tait's conjecture. Every such graph is Hamiltonian. The conjecture was disproved by W. T. Tutte, who constructed a counterexam…

Jørgensen's conjecture. If $G$ is 6-connected and does not have a $K_6$ minor, then $G$ is apex.

Let $G$ be a planar graph, and let $\vec{\chi}(G)$ denote the maximum, over all orientations of $G$, of the minimum number of acyclic colour classes in a vertex colouring. Neumann–…

Let $G$ be a planar graph. Strong Bordeaux Conjecture. If no pair of cycles of length three in $G$ shares an edge and $G$ has no cycle of length five, then $G$ is 3-colorable. This…

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

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

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…