More Like this

1. Rainbow connectivity of randomly perturbed graphs

   https://doi.org/10.1002/jgt.23022  

   Balogh, József; Finlay, John; Palmer, Cory (August 2023, Journal of Graph Theory)

   Abstract In this note we examine the following random graph model: for an arbitrary graph , with quadratic many edges, construct a graph by randomly adding edges to and randomly coloring the edges of with colors. We show that for a large enough constant and , every pair of vertices in are joined by a rainbow path, that is, israinbow connected, with high probability. This confirms a conjecture of Anastos and Frieze, who proved the statement for and resolved the case when and is a function of . 

   more » « less
2. Rainbow subdivisions of cliques

   https://doi.org/10.1002/rsa.21186  

   Jiang, Tao; Letzter, Shoham; Methuku, Abhishek; Yepremyan, Liana (May 2024, Random Structures & Algorithms)

   Abstract We show that for every integer and large , every properly edge‐colored graph on vertices with at least edges contains a rainbow subdivision of . This is sharp up to a polylogarithmic factor. Our proof method exploits the connection between the mixing time of random walks and expansion in graphs. 

   more » « less
3. Rainbow Hamilton cycles in random geometric graphs

   https://doi.org/10.1002/rsa.21201  

   Frieze, Alan; Pérez‐Giménez, Xavier (November 2023, Random Structures & Algorithms)

   Abstract Let be chosen independently and uniformly at random from the unit ‐dimensional cube . Let be given and let . The random geometric graph has vertex set and an edge whenever . We show that if each edge of is colored independently from one of colors and has the smallest value such that has minimum degree at least two, then contains a rainbow Hamilton cycle asymptotically almost surely. 

   more » « less
4. Rainbow Matchings of size $$m$$ in Graphs with Total Color Degree at least $2mn$

   https://doi.org/10.37236/8239  

   Kritschgau, Jürgen (July 2020, The Electronic Journal of Combinatorics)

   null (Ed.)

   The existence of a rainbow matching given a minimum color degree, proper coloring, or triangle-free host graph has been studied extensively. This paper generalizes these problems to edge colored graphs with given total color degree. In particular, we find that if a graph $$G$$ has total color degree $2mn$ and satisfies some other properties, then $$G$$ contains a matching of size $$m$$. These other properties include $$G$$ being triangle-free, $$C_4$$-free, properly colored, or large enough. 

   more » « less
5. The effect of adding randomly weighted edges

   https://doi.org/10.1137/20M1335418  

   Frieze, A. (January 2021, SIAM journal on discrete mathematics)

   We consider the following question. We have a dense regular graph $$G$$ with degree $$\a n$$, where $$\a>0$$ is a constant. We add $m=o(n^2)$ random edges. The edges of the augmented graph $G(m)$ are given independent edge weights $$X(e),e\in E(G(m))$$. We estimate the minimum weight of some specified combinatorial structures. We show that in certain cases, we can obtain the same estimate as is known for the complete graph, but scaled by a factor $$\a^{-1}$$. We consider spanning trees, shortest paths and perfect matchings in (pseudo-random) bipartite graphs. 

   more » « less