Elegantly Colored Paths and Cycles in Edge Colored Random Graphs

DOI10.1137/15M1047106zbMATH Open1391.05229arXiv1403.1453OpenAlexW2963272173MaRDI QIDQ3174699FDOQ3174699

Michael Krivelevich, Lisa Espig, Alan Frieze

Publication date: 18 July 2018

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Path and cycle sub-Ramsey numbers and an edge-colouring conjecture
• Multicoloured Hamilton cycles
• Random graphs.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Polychromatic Hamilton cycles
• The hitting time of rainbow connection number two
• Rainbow Connection of Random Regular Graphs
• On the existence of a factor of degree one of a connected random graph
• Title not available (Why is that?)
• Rainbow connection of sparse random graphs
• Multi-Coloured Hamilton Cycles in Random Edge-Coloured Graphs
• Hamilton cycles in a class of random directed graphs
• Hamilton cycles containing randomly selected edges in random regular graphs
• Rainbow matchings and Hamilton cycles in random graphs
• Rainbow Hamilton cycles in random graphs and hypergraphs
• Rainbow hamilton cycles in random graphs

Cited In (5)

• The threshold for the full perfect matching color profile in a random coloring of random graphs
• Pattern Colored Hamilton Cycles in Random Graphs
• Colorful Hamilton Cycles in Random Graphs
• On the number of alternating paths in random graphs
• Color‐biased 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)