Bang-Jensen et al.'s tightness conjecture for the cycle-transversal bound

From papers

Let τ(D)\tau(D) denote the minimum size of a vertex set whose deletion makes an oriented graph DD acyclic, and let inv(D)\operatorname{inv}(D) denote its inversion number.

Bang-Jensen et al.'s tightness conjecture. For every positive integer nn, there exists an oriented graph DD such that

τ(D)=nandinv(D)=2n.\tau(D)=n\quad\text{and}\quad\operatorname{inv}(D)=2n.

The conjecture asserts that the general bound inv(D)2τ(D)\operatorname{inv}(D)\leq2\tau(D) is tight for every positive value of the cycle-transversal number; the paper notes it would follow from the dijoin conjecture. The source does not state a resolution.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Guillaume Aubian, Frédéric Havet, Florian Hörsch, Felix Klingelhoefer, Nicolas Nisse, Clément Rambaud and Quentin Vermande, “Problems, proofs, and disproofs on the inversion number”, arXiv:2212.09188 (2022).

Solutions 0

No solutions have been posted yet.