An official website of the United States government
In this paper we study the randomly edge colored graph that is obtained by adding randomly colored random edges to an arbitrary randomly edge colored dense graph. In particular we ask how many colors and how many random edges are needed so that the resultant graph contains a fixed number of edge disjoint rainbow Hamilton cycles w.h.p. We also ask when in the resultant graph every pair of vertices is connected by a rainbow path w.h.p.
more »
« less
Rainbow connectivity of randomly perturbed graphs
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
- Award ID(s):
- 1937241
- PAR ID:
- 10442270
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Journal of Graph Theory
- ISSN:
- 0364-9024
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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
-
Abstract We present an integer programming model to compute the strong rainbow connection number,src(G), of any simple graphG. We introduce several enhancements to the proposed model, including a fast heuristic, and a variable elimination scheme. Moreover, we present a novel lower bound forsrc(G) which may be of independent research interest. We solve the integer program both directly and using an alternative method based on iterative lower bound improvement, the latter of which we show to be highly effective in practice. To our knowledge, these are the first computational methods for the strong rainbow connection problem. We demonstrate the efficacy of our methods by computing the strong rainbow connection numbers of graphs containing up to 379 vertices.more » « less
-
Abstract An edge‐coloured graph is said to berainbowif no colour appears more than once. Extremal problems involving rainbow objects have been a focus of much research over the last decade as they capture the essence of a number of interesting problems in a variety of areas. A particularly intensively studied question due to Keevash, Mubayi, Sudakov and Verstraëte from 2007 asks for the maximum possible average degree of a properly edge‐coloured graph on vertices without a rainbow cycle. Improving upon a series of earlier bounds, Tomon proved an upper bound of for this question. Very recently, Janzer–Sudakov and Kim–Lee–Liu–Tran independently removed the term in Tomon's bound, showing a bound of . We prove an upper bound of for this maximum possible average degree when there is no rainbow cycle. Our result is tight up to the term, and so, it essentially resolves this question. In addition, we observe a connection between this problem and several questions in additive number theory, allowing us to extend existing results on these questions for abelian groups to the case of non‐abelian groups.more » « less
-
Abstract Let be a simple graph and be the chromatic index of . We call a ‐critical graphif for every edge of , where is maximum degree of . Let be an edge of ‐critical graph and be an (proper) edge ‐coloring of . Ane‐fanis a sequence of alternating vertices and distinct edges such that edge is incident with or , is another endvertex of and is missing at a vertex before for each with . In this paper, we prove that if , where and denote the degrees of vertices and , respectively, then colors missing at different vertices of are distinct. Clearly, a Vizing fan is an ‐fan with the restricting that all edges being incident with one fixed endvertex of edge . This result gives a common generalization of several recently developed new results on multifan, double fan, Kierstead path of four vertices, and broom. By treating some colors of edges incident with vertices of low degrees as missing colors, Kostochka and Stiebitz introduced ‐fan. In this paper, we also generalize the ‐fan from centered at one vertex to one edge.more » « less
