Abstract | ||
---|---|---|
In this study we consider a Ramsey property of random d-regular graphs, G(n,d). Let r >= 2 be fixed. Then w.h.p. the edges of G(n,2r) can be colored such that every monochromatic component has order o(n). On the other hand, there exists a constant gamma>0 such that w.h.p., every r-coloring of the edges of G(n,2r+1) must contain a monochromatic cycle of length at least gamma n. We prove an analogous result for random k-out graphs. |
Year | DOI | Venue |
---|---|---|
2020 | 10.1002/jgt.22491 | JOURNAL OF GRAPH THEORY |
Keywords | Field | DocType |
monochromatic components,random k-out graphs,random regular graphs | Graph,Combinatorics,Mathematics | Journal |
Volume | Issue | ISSN |
93.0 | 3.0 | 0364-9024 |
Citations | PageRank | References |
0 | 0.34 | 6 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Michael Anastos | 1 | 2 | 3.42 |
Deepak Bal | 2 | 35 | 7.32 |