412 problems
A planar graph metric is a shortest-path metric on a finite planar graph whose edges have arbitrary weights. The Planar Conjecture. Every metric supported on a finite planar graph…
For every integer and every planar graph whose odd girth is at least , the fractional chromatic number satisfies .
A graph is hypohamiltonian if is non-Hamiltonian and, for every vertex , the graph is Hamiltonian. The conjecture is that the minimum order of a planar hyp…
Every planar graph contains a vertex subset such that the induced subgraph is a forest and .
For each positive integer , consider every set of distinct points such that whenever are distinct. Let have vertex s…
For an integer , let be a simple graph with vertices and exactly … edges. A planar graph on vertices is called saturated here if it has the maximum…
For a finite simple graph , write for its number of edges, and let a subgraph mean an ordinary, not necessarily induced, subgraph. The question is whether, for every real…
Every finite planar graph admits a colouring such that: (i) any two adjacent vertices, adjacent edges, or incident vertex-edge pairs receive dis…
For every simple planar graph with vertices, if denotes the maximum number of vertices in an induced forest of , then .
Let be a planar graph with maximum degree , and let denote the minimum number of colors in a coloring in which vertices at distance at most receive dist…
Let be a planar graph. An odd coloring of 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 -colorable.
Heckman–Thomas planar conjecture. Every subcubic triangle-free planar graph is fractionally -colorable.
Dunbar et al.'s conjecture. If is a planar graph, then
Let be the number of vertices, let be the path on vertices, and let denote the join of graphs. Cvetković–Rowlinson's conjecture. The outerplanar graph on…
Let be a planar graph of girth at least , and let be its maximum degree. Wang–Lih conjecture. For every , there exists such that, if…
Neumann–Lara's conjecture. Every orientation of a planar graph has dichromatic number at most .
Let be an -vertex triangle-free planar graph. A proper 3-coloring of is a vertex coloring with three colors in which adjacent vertices receive different colors. Thomasse…
Let be a -regular, -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 is 6-connected and does not have a minor, then is apex.
Let be a planar graph, and let denote the maximum, over all orientations of , of the minimum number of acyclic colour classes in a vertex colouring. Neumann–…
Let be a planar graph. Strong Bordeaux Conjecture. If no pair of cycles of length three in shares an edge and has no cycle of length five, then is 3-colorable. This…
Wang's conjecture. The D-coloring number of satisfies
Let be a signed planar graph, and let denote the corresponding signed girth parameter; let be the signed projective cube of dimension ,…