Bang-Jensen et al.'s tightness conjecture for the cycle-transversal bound
Bang-Jensen et al.'s tightness conjecture for the cycle-transversal bound
Let denote the minimum size of a vertex set whose deletion makes an oriented graph acyclic, and let denote its inversion number.
Bang-Jensen et al.'s tightness conjecture. For every positive integer , there exists an oriented graph such that
The conjecture asserts that the general bound 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
Sign in to submit a solution.
No solutions have been posted yet.