Bang-Jensen et al.'s dijoin conjecture for inversion number
Bang-Jensen et al.'s dijoin conjecture for inversion number
For digraphs without loops, parallel edges, or -cycles, let and be oriented graphs. The dijoin is formed from their disjoint union by adding an arc for every and . The inversion number is the minimum size of a family of vertex subsets whose successive inversions make acyclic.
Bang-Jensen et al.'s dijoin conjecture. For oriented graphs and ,
The conjecture is trivial when one of the two inversion numbers is zero and is known when their sum is at most , as well as when both are . It is false in general: counterexamples were independently found by Alon et al. and Aubian et al.
Sources & referencesView supporting material
Primary source
Haozhe Wang, Yuxuan Yang and Mei Lu, “The inversion number of dijoins and blow-up digraphs”, arXiv:2404.14937 (2024).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.