The planar graph equilibrium conjecture

From papers

Let GG be a strongly connected planar graph, and let gg denote its undirected girth. A static equilibrium is an equilibrium of the static type, while a 22-chase equilibrium and a WT equilibrium are the cycle-based equilibrium types defined in the paper. Planar graph equilibrium conjecture. All strongly connected planar graphs with

g4g\geq 4

have either a static equilibrium, a 22-chase equilibrium, or a WT equilibrium. The conjecture extends the paper's result for strongly connected outerplanar graphs and is motivated by constructions of strongly connected graphs of girth 55 without cycle-based equilibria, all of which are non-planar; its resolution for general planar graphs remains open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Farid Arthaud, Edan Orzech and Martin Rinard, “Edge-dominance games on graphs”, arXiv:2407.07785 (2024).

Solutions 0

No solutions have been posted yet.