Given graphs $G_1,\ldots,G_s$ all on a common vertex set and a graph $H$ with $e(H) = s$, a copy of $H$ is transversal or rainbow if it contains one edge from each $G_i$. We establish a stability result for transversal Hamilton cycles: the minimum degree required to guarantee a transversal Hamilton cycle can be lowered as long as the graph collection $G_1,\ldots,G_n$ is far in edit distance from several extremal cases. We obtain an analogous result for Hamilton paths. The proof is a combination of our newly developed regularity-blow-up method for transversals, along with the absorption method.
@article{10_37236_13624,
author = {Yangyang Cheng and Katherine Staden},
title = {Stability of transversal {Hamilton} cycles and paths},
journal = {The electronic journal of combinatorics},
year = {2025},
volume = {32},
number = {4},
doi = {10.37236/13624},
zbl = {8120122},
url = {http://geodesic.mathdoc.fr/articles/10.37236/13624/}
}
TY - JOUR
AU - Yangyang Cheng
AU - Katherine Staden
TI - Stability of transversal Hamilton cycles and paths
JO - The electronic journal of combinatorics
PY - 2025
VL - 32
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/13624/
DO - 10.37236/13624
ID - 10_37236_13624
ER -
%0 Journal Article
%A Yangyang Cheng
%A Katherine Staden
%T Stability of transversal Hamilton cycles and paths
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/13624/
%R 10.37236/13624
%F 10_37236_13624
Yangyang Cheng; Katherine Staden. Stability of transversal Hamilton cycles and paths. The electronic journal of combinatorics, Tome 32 (2025) no. 4. doi: 10.37236/13624
