Diameter of the inversion graph

In an oriented graph 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 ℐ ( G ) , is the graph whose vertices are the labelled orientations of G in which two labelled orientations G → 1 and G → 2 of G are adjacent if and only if there is a set X whose inversion transforms G → 1 into G → 2 . In this paper, we study the inversion diameter of a graph which is the diameter of its inversion graph denoted by diam ( ℐ ( 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 ( diam ( ℐ ( G ) ) ≤ 12 ), planar graphs of girth at least 8 ( diam ( ℐ ( G ) ) ≤ 3 ), graphs with maximum degree Δ ( diam ( ℐ ( G ) ) ≤ 2 Δ - 1 ), and graphs with treewidth at most t ( diam ( ℐ ( G ) ) ≤ 2 t ). We also show that determining the inversion diameter of a given graph is NP-hard.