Jackson's Hamiltonicity conjecture for regular oriented graphs

About 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

Primary source

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

Additional 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.

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.