Rainbow trees in uniformly edge‐colored graphs

DOI10.1002/RSA.21103zbMATH Open1522.05087arXiv2105.08315MaRDI QIDQ6074865FDOQ6074865

Authors: Elad Aigner-Horev, Dan Hefetz, Abhiruk Lahiri 

Publication date: 19 October 2023

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: We obtain sufficient conditions for the emergence of spanning and almost-spanning bounded-degree {sl rainbow} trees in various host graphs, having their edges coloured independently and uniformly at random, using a predetermined palette. Our first result asserts that a uniform colouring of $mathbbG(n,omega(1)/n)$, using a palette of size $n$, a.a.s. admits a rainbow copy of any given bounded-degree tree on at most $(1-varepsilon)n$ vertices, where $varepsilon>0$ is arbitrarily small yet fixed. This serves as a rainbow variant of a classical result by Alon, Krivelevich, and Sudakov pertaining to the embedding of bounded-degree almost-spanning prescribed trees in $mathbbG(n,C/n)$, where $C>0$ is independent of $n$. Given an $n$-vertex graph $G$ with minimum degree at least $deltan$, where $delta>0$ is fixed, we use our aforementioned result in order to prove that a uniform colouring of the randomly perturbed graph $GcupmathbbG(n,omega(1)/n)$, using $(1+alpha)n$ colours, where $alpha>0$ is arbitrarily small yet fixed, a.a.s. admits a rainbow copy of any given bounded-degree {sl spanning} tree. This can be viewed as a rainbow variant of a result by Krivelevich, Kwan, and Sudakov who proved that $GcupmathbbG(n,C/n)$, where $C>0$ is independent of $n$, a.a.s. admits a copy of any given bounded-degree spanning tree. Finally, and with $G$ as above, we prove that a uniform colouring of $GcupmathbbG(n,omega(n^{-2}))$ using $n-1$ colours a.a.s. admits a rainbow spanning tree. Put another way, the trivial lower bound on the size of the palette required for supporting a rainbow spanning tree is also sufficient, essentially as soon as the random perturbation a.a.s. has edges.

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

Recommendations

• Universality of random graphs and rainbow embedding
• Rainbow and properly colored spanning trees in edge-colored bipartite graphs
• Rainbow spanning subgraphs in bounded edge-colourings of graphs with large minimum degree
• Rainbow Hamilton cycles in randomly colored randomly perturbed dense graphs
• Edge-disjoint rainbow spanning trees in complete graphs

zbMATH Keywords

edge-coloringrandom graphsrandom perturbationrainbow trees

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• Trees in sparse random graphs
• Embedding nearly-spanning bounded degree trees
• Large bounded degree trees in expanding graphs
• A necessary and sufficient condition for the existence of a heterochromatic spanning tree in a graph
• Closing gaps in problems related to Hamilton cycles in random graphs and hypergraphs
• Adding random edges to dense graphs
• How many random edges make a dense graph hamiltonian?
• EMBEDDING SPANNING BOUNDED DEGREE GRAPHS IN RANDOMLY PERTURBED GRAPHS
• Universality for bounded degree spanning trees in randomly perturbed graphs
• Title not available (Why is that?)
• The longest path in a random graph
• Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
• Title not available (Why is that?)
• Long paths in sparse random graphs
• Tilings in randomly perturbed dense graphs
• On large matchings and cycles in sparse random graphs
• Hamilton \(\ell\)-cycles in randomly perturbed hypergraphs
• Powers of tight Hamilton cycles in randomly perturbed hypergraphs
• Cycles and matchings in randomly perturbed digraphs and hypergraphs
• Hamiltonicity in randomly perturbed hypergraphs
• Random perturbation of sparse graphs
• Multicolored trees in random graphs
• Rainbow matchings and Hamilton cycles in random graphs
• Rainbow Hamilton cycles in random graphs and hypergraphs
• Rainbow Hamilton cycles in random graphs
• Powers of Hamiltonian cycles in randomly augmented graphs
• Power of \(k\) choices and rainbow spanning trees in random graphs
• How many randomly colored edges make a randomly colored dense graph rainbow Hamiltonian or rainbow connected?
• Rainbow Hamilton cycles in randomly colored randomly perturbed dense graphs
• High powers of Hamiltonian cycles in randomly augmented graphs

Cited In (10)

• Rainbow arborescence in random digraphs
• Rainbow spanning trees in complete graphs colored by one‐factorizations
• Rainbow spanning trees in random subgraphs of dense regular graphs
• Edge-disjoint rainbow trees in properly coloured complete graphs
• Powers of Hamilton cycles in dense graphs perturbed by a random geometric graph
• Power of \(k\) choices and rainbow spanning trees in random graphs
• Rainbow Spanning Trees in Randomly Colored \(\boldsymbol{G}_{\boldsymbol{k}-\boldsymbol{out}}\)
• Coloring \(k\)-trees with forbidden monochrome or rainbow triangles
• Universality of random graphs and rainbow embedding
• Rainbow and properly colored spanning trees in edge-colored bipartite graphs

This page was built for publication: Rainbow trees in uniformly edge‐colored graphs

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