Diameter of the inversion graph

In an oriented graph <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mover accent="true"> <mml:mi>G</mml:mi> <mml:mo>→</mml:mo> </mml:mover> </mml:math> , the inversion of a subset <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>X</mml:mi> </mml:math> of vertices consists in reversing the orientation of all arcs with both endvertices in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>X</mml:mi> </mml:math> . The inversion graph of a labelled graph <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>G</mml:mi> </mml:math> , denoted by <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ℐ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , is the graph whose vertices are the labelled orientations of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>G</mml:mi> </mml:math> in which two labelled orientations <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mover accent="true"> <mml:mi>G</mml:mi> <mml:mo>→</mml:mo> </mml:mover> <mml:mn>1</mml:mn> </mml:msub> </mml:math> and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mover accent="true"> <mml:mi>G</mml:mi> <mml:mo>→</mml:mo> </mml:mover> <mml:mn>2</mml:mn> </mml:msub> </mml:math> of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>G</mml:mi> </mml:math> are adjacent if and only if there is a set <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>X</mml:mi> </mml:math> whose inversion transforms <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mover accent="true"> <mml:mi>G</mml:mi> <mml:mo>→</mml:mo> </mml:mover> <mml:mn>1</mml:mn> </mml:msub> </mml:math> into <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mover accent="true"> <mml:mi>G</mml:mi> <mml:mo>→</mml:mo> </mml:mover> <mml:mn>2</mml:mn> </mml:msub> </mml:math> . In this paper, we study the inversion diameter of a graph which is the diameter of its inversion graph denoted by <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi mathvariant="normal">diam</mml:mi> <mml:mo>(</mml:mo> <mml:mi>ℐ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>G</mml:mi> </mml:math> contained in one of the following graph classes: planar graphs ( <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi mathvariant="normal">diam</mml:mi> <mml:mo>(</mml:mo> <mml:mi>ℐ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> <mml:mo>)</mml:mo> <mml:mo>≤</mml:mo> <mml:mn>12</mml:mn> </mml:mrow> </mml:math> ), planar graphs of girth at least 8 ( <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi mathvariant="normal">diam</mml:mi> <mml:mo>(</mml:mo> <mml:mi>ℐ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> <mml:mo>)</mml:mo> <mml:mo>≤</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> ), graphs with maximum degree <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Δ</mml:mi> </mml:math> ( <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi mathvariant="normal">diam</mml:mi> <mml:mo>(</mml:mo> <mml:mi>ℐ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> <mml:mo>)</mml:mo> <mml:mo>≤</mml:mo> <mml:mn>2</mml:mn> <mml:mi>Δ</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> ), and graphs with treewidth at most <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>t</mml:mi> </mml:math> ( <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi mathvariant="normal">diam</mml:mi> <mml:mo>(</mml:mo> <mml:mi>ℐ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> <mml:mo>)</mml:mo> <mml:mo>≤</mml:mo> <mml:mn>2</mml:mn> <mml:mi>t</mml:mi> </mml:mrow> </mml:math> ). We also show that determining the inversion diameter of a given graph is NP-hard.