Polynomial Hamiltonian-cycle conjecture for split digraphs with bounded independent sets

A split digraph is a digraph D=(V1,V2;A)D=(V_1,V_2;A) whose vertex set is the disjoint union of an independent set V1V_1 and a set V2V_2 inducing a semicomplete digraph. A Hamiltonian cycle is a directed cycle containing every vertex exactly once.

Bounded-independent-set conjecture. For every fixed integer kk, the Hamiltonian-cycle problem is polynomial-time solvable for the class of split digraphs D=(V1,V2;A)D=(V_1,V_2;A) in which the independent set satisfies V1k|V_1|\leq k.

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

Never refreshed

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

Solutions 0

No solutions have been posted yet.