pith. machine review for the scientific record. sign in

arxiv: 2501.00998 · v2 · submitted 2025-01-02 · 🧮 math.CO

Recognition: unknown

Transversal Hamilton cycles in digraph collections

Authors on Pith no claims yet
classification 🧮 math.CO
keywords transversaldigraphcollectionsghouila-hourihamiltonmathcalmethodproved
0
0 comments X
read the original abstract

Given a collection $\mathcal{D} =\{D_1,D_2,\ldots,D_m\}$ of digraphs on the common vertex set $V$, an $m$-edge digraph $H$ with vertices in $V$ is \textit{transversal} in $\mathcal{D}$ if there exists a bijection $\varphi :E(H)\rightarrow [m]$ such that $e \in E(D_{\varphi(e)})$ for all $e\in E(H)$. Ghouila-Houri proved that any $n$-vertex digraph with minimum semi-degree at least $\frac{n}{2}$ contains a directed Hamilton cycle. In this paper, we provide a transversal generalization of Ghouila-Houri's theorem, thereby solving a problem proposed by Chakraborti, Kim, Lee and Seo. Our proof utilizes the absorption method for transversals, the regularity method for digraph collections, as well as the transversal blow-up lemma and the related machinery. As an application, when $n$ is sufficiently large, our result implies the transversal version of Dirac's theorem, which was proved by Joos and Kim.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.