Hamilton decompositions of regular tripartite tournaments
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918095091662848 |
|---|---|
| author | Di Braccio, Francesco Lada, Joanna Patel, Viresh Pehova, Yani Skokan, Jozef |
| author_facet | Di Braccio, Francesco Lada, Joanna Patel, Viresh Pehova, Yani Skokan, Jozef |
| contents | Kühn and Osthus conjectured in 2013 that regular tripartite tournaments are decomposable into Hamilton cycles. Somewhat surprisingly, Granet gave a simple counterexample to this conjecture almost 10 years later. In this paper, we show that the conjecture of Kühn and Osthus nevertheless holds in an approximate sense, by proving that every regular tripartite tournament admits an approximate decomposition into Hamilton cycles. We also study Hamilton cycle packings of directed graphs in the same regime, and show that for large $n$, every balanced tripartite digraph on $3n$ vertices which is $d$-regular for $d\ge (1+o(1))n$ admits a Hamilton decomposition. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_12460 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Hamilton decompositions of regular tripartite tournaments Di Braccio, Francesco Lada, Joanna Patel, Viresh Pehova, Yani Skokan, Jozef Combinatorics Kühn and Osthus conjectured in 2013 that regular tripartite tournaments are decomposable into Hamilton cycles. Somewhat surprisingly, Granet gave a simple counterexample to this conjecture almost 10 years later. In this paper, we show that the conjecture of Kühn and Osthus nevertheless holds in an approximate sense, by proving that every regular tripartite tournament admits an approximate decomposition into Hamilton cycles. We also study Hamilton cycle packings of directed graphs in the same regime, and show that for large $n$, every balanced tripartite digraph on $3n$ vertices which is $d$-regular for $d\ge (1+o(1))n$ admits a Hamilton decomposition. |
| title | Hamilton decompositions of regular tripartite tournaments |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2507.12460 |