Inversion Diameter of Planar Graphs

Abstract

Given an oriented graph $\vec{G}$ and a subset of vertices $X \subseteq V(\vec{G})$, the \emph{inversion} of $X$ is the operation that reverses the orientation of every arc with both endpoints in $X$. For a simple graph $G$, the inversion diameter $\operatorname{diam}(I(G))$ is the maximum distance between two orientations of $G$ under inversions of vertex sets. We prove the sharp bound \[ \operatorname{diam}(I(G))\le 2χ_a(G)-2, \] where $χ_a(G)$ is the acyclic chromatic number. Consequently, every planar graph has inversion diameter at most $8$, improving the previously known bound $12$. Using strong-degeneracy arguments, we also obtain upper bounds $7$, $5$, and $4$ for planar graphs of girth at least $4$, $5$, and $6$, respectively.

Disclosure

“ng the preparation of the manuscript. It was used to improve the language, organization, and presentation of the manuscript and to assist in revising preliminary drafts. In particular, the idea in Theorem 1.1 arose from an interaction with ChatGPT. After using this tool the authors reviewed and edited the content as needed and take full responsibility for the content of the publication. No mathematical statement, proof, constant, numerical value or reference in this paper was genera”

PDF page 15

Classification

Brainstorming or outlining

Multiplier

2

Verified

2026-08-22T18:23:37.717313Z

Structural counts