Rainbow connectivity of randomly perturbed graphs

József Balogh, John Finlay, Cory Palmer

Research output: Contribution to journalArticlepeer-review


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

Original languageEnglish (US)
JournalJournal of Graph Theory
StateAccepted/In press - 2023


  • perturbed graph
  • rainbow connectivity
  • random edge-coloring

ASJC Scopus subject areas

  • Geometry and Topology
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Rainbow connectivity of randomly perturbed graphs'. Together they form a unique fingerprint.

Cite this