Elegantly colored paths and cycles in edge colored random graphs

DOI10.1137/15M1047106MaRDI QIDQ3174699zbMATH OpenOpenAlexFDO

Authors Lisa Espig, Michael Krivelevich, Alan Frieze

Publication date 18 July 2018

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1403.1453

zbMATH Keywords

random graphsrandomly edge coloredzebraic

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Eulerian and Hamiltonian graphs (05C45) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

Abstract: We first consider the following problem. We are given a fixed perfect matching $M$ of $[n]$ and we add random edges one at a time until there is a Hamilton cycle containing $M$. We show that w.h.p. the hitting time for this event is the same as that for the first time there are no isolated vertices in the graph induced by the random edges. We then use this result for the following problem. We generate random edges and randomly color them black or white. A path/cycle is said to emph{zebraic} if the colors alternate along the path. We show that w.h.p. the hitting time for a zebraic Hamilton cycle coincides with every vertex meeting at least one edge of each color. We then consider some related problems and extend to multiple colors. We also briefly consider directed versions.

Recommendations

• Pattern colored Hamilton cycles in random graphs
• Color‐biased Hamilton cycles in random graphs
• Colorful Hamilton Cycles in Random Graphs
• Rainbow Hamilton cycles in random regular graphs
• Multi-Coloured Hamilton Cycles in Random Edge-Coloured Graphs

Cites work

• scientific article; zbMATH DE number 3825881 (Why is no real title available?)
• scientific article; zbMATH DE number 17675 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Hamilton cycles containing randomly selected edges in random regular graphs
• Hamilton cycles in a class of random directed graphs
• Multi-Coloured Hamilton Cycles in Random Edge-Coloured Graphs
• Multicoloured Hamilton cycles
• On the existence of a factor of degree one of a connected random graph
• Path and cycle sub-Ramsey numbers and an edge-colouring conjecture
• Polychromatic Hamilton cycles
• Rainbow Hamilton cycles in random graphs
• Rainbow Hamilton cycles in random graphs and hypergraphs
• Rainbow connection of random regular graphs
• Rainbow connection of sparse random graphs
• Rainbow matchings and Hamilton cycles in random graphs
• Random graphs.
• The hitting time of rainbow connection number two
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(5)

• On the number of alternating paths in random graphs
• Colorful Hamilton Cycles in Random Graphs
• The threshold for the full perfect matching color profile in a random coloring of random graphs
• Color‐biased Hamilton cycles in random graphs
• Pattern colored Hamilton cycles in random graphs

This page was built for publication: Elegantly colored paths and cycles in edge colored random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3174699)