The planar graph equilibrium conjecture
The planar graph equilibrium conjecture
Let be a strongly connected planar graph, and let denote its undirected girth. A static equilibrium is an equilibrium of the static type, while a -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
have either a static equilibrium, a -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 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
Sign in to submit a solution.
No solutions have been posted yet.