Polynomial Hamiltonian-cycle conjecture for split digraphs with bounded independent sets
Polynomial Hamiltonian-cycle conjecture for split digraphs with bounded independent sets
A split digraph is a digraph whose vertex set is the disjoint union of an independent set and a set inducing a semicomplete digraph. A Hamiltonian cycle is a directed cycle containing every vertex exactly once.
Bounded-independent-set conjecture. For every fixed integer , the Hamiltonian-cycle problem is polynomial-time solvable for the class of split digraphs in which the independent set satisfies .
The conjecture proposes a polynomial algorithm for each fixed bound on the independent-set size. The source motivates it using the preceding fixed-vertex-extension conjecture, but gives no resolution evidence.
Sources & referencesView supporting material
Primary source
Joergen Bang-Jensen and Yun Wang, “Strong arc decompositions of split digraphs”, arXiv:2309.06904 (2023).
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.