{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T15:06:34Z","timestamp":1779375994414,"version":"3.53.1"},"reference-count":18,"publisher":"MathDoc\/Centre Mersenne","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>\n                    In an oriented graph\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mover accent=\"true\">\n                        <mml:mi>G<\/mml:mi>\n                        <mml:mo>\u2192<\/mml:mo>\n                      <\/mml:mover>\n                    <\/mml:math>\n                    , the inversion of a subset\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>X<\/mml:mi>\n                    <\/mml:math>\n                    of vertices consists in reversing the orientation of all arcs with both endvertices in\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>X<\/mml:mi>\n                    <\/mml:math>\n                    . The inversion graph of a labelled graph\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>G<\/mml:mi>\n                    <\/mml:math>\n                    , denoted by\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mi>\u2110<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mi>G<\/mml:mi>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    , is the graph whose vertices are the labelled orientations of\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>G<\/mml:mi>\n                    <\/mml:math>\n                    in which two labelled orientations\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:msub>\n                        <mml:mover accent=\"true\">\n                          <mml:mi>G<\/mml:mi>\n                          <mml:mo>\u2192<\/mml:mo>\n                        <\/mml:mover>\n                        <mml:mn>1<\/mml:mn>\n                      <\/mml:msub>\n                    <\/mml:math>\n                    and\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:msub>\n                        <mml:mover accent=\"true\">\n                          <mml:mi>G<\/mml:mi>\n                          <mml:mo>\u2192<\/mml:mo>\n                        <\/mml:mover>\n                        <mml:mn>2<\/mml:mn>\n                      <\/mml:msub>\n                    <\/mml:math>\n                    of\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>G<\/mml:mi>\n                    <\/mml:math>\n                    are adjacent if and only if there is a set\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>X<\/mml:mi>\n                    <\/mml:math>\n                    whose inversion transforms\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:msub>\n                        <mml:mover accent=\"true\">\n                          <mml:mi>G<\/mml:mi>\n                          <mml:mo>\u2192<\/mml:mo>\n                        <\/mml:mover>\n                        <mml:mn>1<\/mml:mn>\n                      <\/mml:msub>\n                    <\/mml:math>\n                    into\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:msub>\n                        <mml:mover accent=\"true\">\n                          <mml:mi>G<\/mml:mi>\n                          <mml:mo>\u2192<\/mml:mo>\n                        <\/mml:mover>\n                        <mml:mn>2<\/mml:mn>\n                      <\/mml:msub>\n                    <\/mml:math>\n                    . In this paper, we study the inversion diameter of a graph which is the diameter of its inversion graph denoted by\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mi mathvariant=\"normal\">diam<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mi>\u2110<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mi>G<\/mml:mi>\n                        <mml:mo>)<\/mml:mo>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    . 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\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>G<\/mml:mi>\n                    <\/mml:math>\n                    contained in one of the following graph classes: planar graphs (\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mi mathvariant=\"normal\">diam<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mi>\u2110<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mi>G<\/mml:mi>\n                        <mml:mo>)<\/mml:mo>\n                        <mml:mo>)<\/mml:mo>\n                        <mml:mo>\u2264<\/mml:mo>\n                        <mml:mn>12<\/mml:mn>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    ), planar graphs of girth at least 8 (\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mi mathvariant=\"normal\">diam<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mi>\u2110<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mi>G<\/mml:mi>\n                        <mml:mo>)<\/mml:mo>\n                        <mml:mo>)<\/mml:mo>\n                        <mml:mo>\u2264<\/mml:mo>\n                        <mml:mn>3<\/mml:mn>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    ), graphs with maximum degree\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>\u0394<\/mml:mi>\n                    <\/mml:math>\n                    (\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mi mathvariant=\"normal\">diam<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mi>\u2110<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mi>G<\/mml:mi>\n                        <mml:mo>)<\/mml:mo>\n                        <mml:mo>)<\/mml:mo>\n                        <mml:mo>\u2264<\/mml:mo>\n                        <mml:mn>2<\/mml:mn>\n                        <mml:mi>\u0394<\/mml:mi>\n                        <mml:mo>-<\/mml:mo>\n                        <mml:mn>1<\/mml:mn>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    ), and graphs with treewidth at most\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>t<\/mml:mi>\n                    <\/mml:math>\n                    (\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mi mathvariant=\"normal\">diam<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mi>\u2110<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mi>G<\/mml:mi>\n                        <mml:mo>)<\/mml:mo>\n                        <mml:mo>)<\/mml:mo>\n                        <mml:mo>\u2264<\/mml:mo>\n                        <mml:mn>2<\/mml:mn>\n                        <mml:mi>t<\/mml:mi>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    ).\n                  <\/jats:p>\n                  <jats:p>We also show that determining the inversion diameter of a given graph is NP-hard.<\/jats:p>","DOI":"10.5802\/igt18","type":"journal-article","created":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T09:28:36Z","timestamp":1775122116000},"page":"49-88","source":"Crossref","is-referenced-by-count":0,"title":["Diameter of the inversion graph"],"prefix":"10.5802","volume":"3","author":[{"given":"Fr\u00e9d\u00e9ric","family":"Havet","sequence":"first","affiliation":[{"name":"Universit\u00e9 C\u00f4te d\u2019Azur, CNRS, Inria, I3S, Sophia Antipolis, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Florian","family":"H\u00f6rsch","sequence":"additional","affiliation":[{"name":"CISPA, Saarbr\u00fccken, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cl\u00e9ment","family":"Rambaud","sequence":"additional","affiliation":[{"name":"Universit\u00e9 C\u00f4te d\u2019Azur, CNRS, Inria, I3S, Sophia Antipolis, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"3842","published-online":{"date-parts":[[2026,4,2]]},"reference":[{"issue":"1","key":"key2026052116243522040_1","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1137\/23M1547135","article-title":"Invertibility of Digraphs and Tournaments","volume":"38","author":"Alon, Noga","year":"2024","unstructured":"[1] Alon, Noga; Powierski, Emil; Savery, Michael; Scott, Alex; Wilmer, Elizabeth Invertibility of Digraphs and Tournaments, SIAM J. Discrete Math., Volume 38 (2024) no. 1, pp. 327-347","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"key2026052116243522040_2","doi-asserted-by":"publisher","DOI":"10.37236\/12983","article-title":"Problems, Proofs, and Disproofs on the Inversion Number","volume":"32","author":"Aubian, Guillaume","year":"2025","unstructured":"[2] Aubian, Guillaume; Havet, Fr\u00e9d\u00e9ric; H\u00f6rsch, Florian; Kingelhoefer, Felix; Nisse, N.; Rambaud, Cl\u00e9ment; Vermande, Quentin Problems, Proofs, and Disproofs on the Inversion Number, Electron. J. Comb., Volume 32 (2025) no. 1, P1.42, 15 pages","journal-title":"Electron. J. Comb."},{"issue":"2","key":"key2026052116243522040_3","doi-asserted-by":"publisher","DOI":"10.46298\/DMTCS.7474","article-title":"On the inversion number of oriented graphs","volume":"23","author":"Bang-Jensen, J\u00f8rgen","year":"2021","unstructured":"[3] Bang-Jensen, J\u00f8rgen; Ferreira da Silva, Jonas Costa; Havet, Fr\u00e9d\u00e9ric On the inversion number of oriented graphs, Discrete Math. Theor. Comput. Sci., Volume 23 (2021) no. 2, 8, 29 pages","journal-title":"Discrete Math. Theor. Comput. Sci."},{"issue":"13-14","key":"key2026052116243522040_4","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1016\/j.crma.2010.06.022","article-title":"Inversion dans les tournois","volume":"348","author":"Belkhechine, Houmem","year":"2010","unstructured":"[4] Belkhechine, Houmem; Bouaziz, Moncef; Boudabbous, Imed; Pouzet, Maurice Inversion dans les tournois, Comptes Rendus. Math\u00e9matique, Volume 348 (2010) no. 13-14, pp. 703-707","journal-title":"Comptes Rendus. Math\u00e9matique"},{"key":"key2026052116243522040_5","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84628-970-5","author":"Bondy, J. A.","year":"2008","unstructured":"[5] Bondy, J. A.; Murty, U. S. R. Graph Theory, Graduate Texts in Mathematics, Springer, 2008","journal-title":"Graph Theory"},{"key":"key2026052116243522040_6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53622-3","author":"Diestel, Reinhard","year":"2017","unstructured":"[6] Diestel, Reinhard Graph Theory, Springer Berlin, 2017","journal-title":"Graph Theory"},{"key":"key2026052116243522040_7","author":"Duron, Julien","year":"2023","unstructured":"[7] Duron, Julien; Havet, Fr\u00e9d\u00e9ric; H\u00f6rsch, Florian; Rambaud, Cl\u00e9ment On the minimum number of inversions to make a digraph k-(arc-)strong (2023)","journal-title":"On the minimum number of inversions to make a digraph <span class=\"mathjax-formula\" data-tex=\"$k$\"><math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mi>k<\/mi><\/math><\/span>-(arc-)strong"},{"issue":"3","key":"key2026052116243522040_8","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","article-title":"Some simplified NP-complete graph problems","volume":"1","author":"Garey, Michael R.","year":"1976","unstructured":"[8] Garey, Michael R.; Johnson, David S.; Stockmeyer, Larry Some simplified NP-complete graph problems, Theor. Comput. Sci., Volume 1 (1976) no. 3, pp. 237-267","journal-title":"Theor. Comput. Sci."},{"key":"key2026052116243522040_9","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1007\/BF02764716","article-title":"Acyclic coloring of planar graphs","volume":"14","author":"Gr\u00fcnbaum, Branko","year":"1973","unstructured":"[9] Gr\u00fcnbaum, Branko Acyclic coloring of planar graphs, Isr. J. Math., Volume 14 (1973), pp. 390-408","journal-title":"Isr. J. Math."},{"key":"key2026052116243522040_10","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/j.ejc.2017.06.019","article-title":"On the generalised colouring numbers of graphs that exclude a fixed minor","volume":"66","author":"van den Heuvel, Jan","year":"2017","unstructured":"[10] van den Heuvel, Jan; Ossona de Mendez, Patrice; Quiroz, Daniel; Rabinovich, Roman; Siebertz, Sebastian On the generalised colouring numbers of graphs that exclude a fixed minor, Eur. J. Comb., Volume 66 (2017), pp. 129-144","journal-title":"Eur. J. Comb."},{"key":"key2026052116243522040_11","author":"Karp, Richard M.","year":"1972","unstructured":"[11] Karp, Richard M. Reducibility among Combinatorial Problems, Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, Springer, 1972","journal-title":"Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations"},{"issue":"4","key":"key2026052116243522040_12","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1002\/(SICI)1097-0118(199704)24:4<331::AID-JGT5>3.0.CO;2-P","article-title":"Acyclic and oriented chromatic numbers of graphs","volume":"24","author":"Kostochka, Alexandr V.","year":"1997","unstructured":"[12] Kostochka, Alexandr V.; Sopena, \u00c9ric; Zhu, Xuding Acyclic and oriented chromatic numbers of graphs, J. Graph Theory, Volume 24 (1997) no. 4, pp. 331-340","journal-title":"J. Graph Theory"},{"key":"key2026052116243522040_13","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.jsc.2013.09.003","article-title":"Practical graph isomorphism, II","volume":"60","author":"McKay, Brendan D.","year":"2014","unstructured":"[13] McKay, Brendan D.; Piperno, Adolfo Practical graph isomorphism, II, J. Symb. Comput., Volume 60 (2014), pp. 94-112","journal-title":"J. Symb. Comput."},{"issue":"4","key":"key2026052116243522040_14","doi-asserted-by":"publisher","DOI":"10.3390\/a11040052","article-title":"Introduction to Reconfiguration","volume":"11","author":"Nishimura, Naomi","year":"2018","unstructured":"[14] Nishimura, Naomi Introduction to Reconfiguration, Algorithms (Basel), Volume 11 (2018) no. 4, 52, 25 pages","journal-title":"Algorithms (Basel)"},{"issue":"4","key":"key2026052116243522040_15","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(94)00088-3","article-title":"Good and semi-strong colorings of oriented planar graphs","volume":"51","author":"Raspaud, Andr\u00e9","year":"1994","unstructured":"[15] Raspaud, Andr\u00e9; Sopena, \u00c9ric Good and semi-strong colorings of oriented planar graphs, Inf. Process. Lett., Volume 51 (1994) no. 4, pp. 171-174","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"key2026052116243522040_16","first-page":"32","article-title":"Completeness in the Polynomial-Time Hierarchy A Compendium","volume":"33","author":"Schaefer, Marcus","year":"2002","unstructured":"[16] Schaefer, Marcus; Umans, Christopher Completeness in the Polynomial-Time Hierarchy A Compendium, Sigact News - SIGACT, Volume 33 (2002) no. 3, pp. 32-49","journal-title":"Sigact News - SIGACT"},{"key":"key2026052116243522040_17","doi-asserted-by":"publisher","DOI":"10.5281\/ZENODO.5233953","article-title":"GNU Parallel 20210822 (\u2019Kabul\u2019)","author":"Tange, Ole","year":"2021","unstructured":"[17] Tange, Ole GNU Parallel 20210822 (\u2019Kabul\u2019), 2021 (https:\/\/www.gnu.org\/software\/parallel\/)"},{"issue":"1","key":"key2026052116243522040_18","first-page":"37","article-title":"Acyclic, star and oriented colourings of graph subdivisions","volume":"7","author":"Wood, David R.","year":"2005","unstructured":"[18] Wood, David R. Acyclic, star and oriented colourings of graph subdivisions, Discrete Math. Theor. Comput. Sci., Volume 7 (2005) no. 1, pp. 37-50","journal-title":"Discrete Math. Theor. Comput. Sci."}],"container-title":["Innovations in Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/igt.centre-mersenne.org\/item\/10.5802\/igt18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T14:24:45Z","timestamp":1779373485000},"score":1,"resource":{"primary":{"URL":"https:\/\/igt.centre-mersenne.org\/articles\/10.5802\/igt18\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,2]]},"references-count":18,"alternative-id":["10.5802\/igt18"],"URL":"https:\/\/doi.org\/10.5802\/igt18","relation":{},"ISSN":["3050-743X"],"issn-type":[{"value":"3050-743X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,2]]}}}