In an oriented graph $\vec{G}$, the inversion of a subset $X$ of vertices consists in reversing the orientation of all arcs with both endvertices in $X$. The inversion graph of a labelled graph $G$, denoted by ${\mathcal{I}}(G)$, is the graph whose vertices are the labelled orientations of $G$ in which two labelled orientations $\vec{G}_1$ and $\vec{G}_2$ of $G$ are adjacent if and only if there is a set $X$ whose inversion transforms $\vec{G}_1$ into $\vec{G}_2$. In this paper, we study the inversion diameter of a graph which is the diameter of its inversion graph denoted by $\mathrm{diam}(\mathcal{I}(G))$. We show that the inversion diameter is tied to the star chromatic number, the acyclic chromatic number and the oriented chromatic number. Thus a graph class has bounded inversion diameter if and only if it also has bounded star chromatic number, acyclic chromatic number and oriented chromatic number. We give some upper bounds on the inversion diameter of a graph $G$ contained in one of the following graph classes: planar graphs ($\mathrm{diam}(\mathcal{I}(G)) \le 12$), planar graphs of girth at least 8 ($\mathrm{diam}(\mathcal{I}(G)) \le 3$), graphs with maximum degree $\Delta $ ($\mathrm{diam}(\mathcal{I}(G)) \le 2\Delta -1$), and graphs with treewidth at most $t$ ($\mathrm{diam}(\mathcal{I}(G)) \le 2t$).
We also show that determining the inversion diameter of a given graph is NP-hard.
Accepted:
Published online:
Keywords: inversion graph, diameter, orientation, reconfiguration
Havet, Frédéric 1 ; Hörsch, Florian 2 ; Rambaud, Clément 1
CC-BY 4.0
@article{IGT_2026__3__49_0,
author = {Havet, Fr\'ed\'eric and H\"orsch, Florian and Rambaud, Cl\'ement},
title = {Diameter of the inversion graph},
journal = {Innovations in Graph Theory},
pages = {49--88},
year = {2026},
publisher = {Stichting Innovations in Graph Theory},
volume = {3},
doi = {10.5802/igt18},
language = {en},
url = {https://igt.centre-mersenne.org/articles/10.5802/igt18/}
}
TY - JOUR AU - Havet, Frédéric AU - Hörsch, Florian AU - Rambaud, Clément TI - Diameter of the inversion graph JO - Innovations in Graph Theory PY - 2026 SP - 49 EP - 88 VL - 3 PB - Stichting Innovations in Graph Theory UR - https://igt.centre-mersenne.org/articles/10.5802/igt18/ DO - 10.5802/igt18 LA - en ID - IGT_2026__3__49_0 ER -
%0 Journal Article %A Havet, Frédéric %A Hörsch, Florian %A Rambaud, Clément %T Diameter of the inversion graph %J Innovations in Graph Theory %D 2026 %P 49-88 %V 3 %I Stichting Innovations in Graph Theory %U https://igt.centre-mersenne.org/articles/10.5802/igt18/ %R 10.5802/igt18 %G en %F IGT_2026__3__49_0
Havet, Frédéric; Hörsch, Florian; Rambaud, Clément. Diameter of the inversion graph. Innovations in Graph Theory, Volume 3 (2026), pp. 49-88. doi: 10.5802/igt18
[1] Invertibility of Digraphs and Tournaments, SIAM J. Discrete Math., Volume 38 (2024) no. 1, pp. 327-347 | DOI | MR | Zbl
[2] Problems, Proofs, and Disproofs on the Inversion Number, Electron. J. Comb., Volume 32 (2025) no. 1, Paper no. P1.42, 15 pages | DOI | MR | Zbl
[3] On the inversion number of oriented graphs, Discrete Math. Theor. Comput. Sci., Volume 23 (2021) no. 2, Paper no. 8, 29 pages | DOI | MR
[4] Inversion dans les tournois, Comptes Rendus. Mathématique, Volume 348 (2010) no. 13-14, pp. 703-707 | Zbl | DOI | Numdam
[5] Graph Theory, Graduate Texts in Mathematics, Springer, 2008 | DOI | Zbl | MR
[6] Graph Theory, Springer Berlin, 2017 | DOI | Zbl
[7] On the minimum number of inversions to make a digraph -(arc-)strong (2023) | arXiv
[8] Some simplified NP-complete graph problems, Theor. Comput. Sci., Volume 1 (1976) no. 3, pp. 237-267 | DOI | Zbl | MR
[9] Acyclic coloring of planar graphs, Isr. J. Math., Volume 14 (1973), pp. 390-408 | DOI | Zbl | MR
[10] On the generalised colouring numbers of graphs that exclude a fixed minor, Eur. J. Comb., Volume 66 (2017), pp. 129-144 | DOI | Zbl | MR
[11] Reducibility among Combinatorial Problems, Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, Springer, 1972
[12] Acyclic and oriented chromatic numbers of graphs, J. Graph Theory, Volume 24 (1997) no. 4, pp. 331-340 | Zbl | DOI | MR
[13] Practical graph isomorphism, II, J. Symb. Comput., Volume 60 (2014), pp. 94-112 | DOI | Zbl | MR
[14] Introduction to Reconfiguration, Algorithms (Basel), Volume 11 (2018) no. 4, Paper no. 52, 25 pages | DOI | Zbl | MR
[15] Good and semi-strong colorings of oriented planar graphs, Inf. Process. Lett., Volume 51 (1994) no. 4, pp. 171-174 | Zbl | MR | DOI
[16] Completeness in the Polynomial-Time Hierarchy A Compendium, Sigact News - SIGACT, Volume 33 (2002) no. 3, pp. 32-49
[17] GNU Parallel 20210822 (’Kabul’), 2021 (https://www.gnu.org/software/parallel/) | DOI
[18] Acyclic, star and oriented colourings of graph subdivisions, Discrete Math. Theor. Comput. Sci., Volume 7 (2005) no. 1, pp. 37-50 | Zbl | MR
Cited by Sources: