Back to Search
Start Over
An approximate version of Jackson's conjecture
- Publication Year :
- 2019
-
Abstract
- In 1981 Jackson showed that the diregular bipartite tournament (a complete bipartite graph whose edges are oriented so that every vertex has the same in- and outdegree) contains a Hamilton cycle, and conjectured that in fact the edge set of it can be partitioned into Hamilton cycles. We prove an approximate version of this conjecture: For every $c>1/2$ and $\varepsilon>0$ there exists $n_0$ such that every $cn$-regular bipartite digraph on $2n\geq n_0$ vertices contains $(1-\varepsilon)cn$ edge-disjoint Hamilton cycles.
- Subjects :
- Mathematics - Combinatorics
05C20, 05C45, 05C70
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1907.08479
- Document Type :
- Working Paper