← All problems

Jackson's Hamiltonicity conjecture for regular oriented graphs

16 years old · traced to

Let GG be an oriented graph, meaning a directed graph with at most one directed edge between each pair of vertices. It is dd-regular when every vertex has dd in-neighbours and dd out-neighbours.

Jackson's conjecture. For each d>2d>2, every dd-regular oriented graph on n≤4d+1n\leq 4d+1 vertices has a Hamilton cycle.

The conjecture asserts that regularity substantially lowers the degree threshold for Hamiltonicity in oriented graphs. The paper proves it for sufficiently large nn as a consequence of a stronger dense cycle-cover theorem, but the stated conjecture is not presented as completely resolved here.

References

3 papers in this index state this conjecture (2010–2023). The statement above is taken from the most recent of them; the others are arXiv:2203.10112, arXiv:1006.0590.

Source: Allan Lo, Viresh Patel and Mehmet Akif Yıldız, “Cycle Partitions in Dense Regular Digraphs and Oriented Graphs”, arXiv:2309.11677 (2025).

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.