Diameter of the inversion graph
Belkhechine and his team in 2010 introduced the concept of inversion as follows. In an oriented graph \(G\), if \(X\) is a set of vertices then the inversion of \(X\) consists in reversing the orientation of all arcs with both endvertices in \(X\) and the inversion number is the minimum number of inversions that transform \(G\) into a directed acyclic graph. In this paper the authors probed the inversion diameter of a graph which is the diameter of its inversion graph and established that the inversion diameter is linked to the star chromatic number, the acyclic chromatic number and the oriented chromatic number. They also found certain upper bounds on the inversion diameter of a graph \(G\) contained in specific classes of planar graphs,graphs with particular treewidth and graphs with given maximum degree. They also proved an NP complete result concerning inversion diameter of a given graph. They also raised some open questions for the researchers working in this area.
- Acyclic and oriented chromatic numbers of graphs
- Acyclic colorings of planar graphs
- Good and semi-strong colorings of oriented planar graphs
- Graph theory
- Graph theory
- scientific article; zbMATH DE number 2159660 (Why is no real title available?)
- Introduction to reconfiguration
- Inversions in tournaments
- Invertibility of Digraphs and Tournaments
- On the generalised colouring numbers of graphs that exclude a fixed minor
- On the minimum number of inversions to make a digraph k-(arc-)strong (extended abstract)
- Practical graph isomorphism. II.
- Problems, proofs, and disproofs on the inversion number
- Some simplified NP-complete graph problems
This page was built for publication: Diameter of the inversion graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7240349)
