Key points are not available for this paper at this time.
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 I (G), is the graph whose vertices are the labelled orientations of G in which two labelled orientations G₁ and G₂ of G are adjacent if and only if there is an inversion X transforming G₁ into G₂. In this paper, we study the inversion diameter of a graph which is the diameter of its inversion graph denoted by diam (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 (diam (I (G) ) 12), planar graphs of girth 8 (diam (I (G) ) 3), graphs with maximum degree (diam (I (G) ) 2 -1), graphs with treewidth at mots t (diam (I (G) ) 2t). We also show that determining the inversion diameter of a given graph is NP-hard.
Havet et al. (Tue,) studied this question.