Some Remarks on Rainbow Connectivity

Nina Kamčev, Michael Krivelevich, Benny Sudakov

Research output: Contribution to journalArticleResearchpeer-review

9 Citations (Scopus)

Abstract

An edge (vertex) colored graph is rainbow-connected if there is a rainbow path between any two vertices, i.e. a path all of whose edges (internal vertices) carry distinct colors. Rainbow edge (vertex) connectivity of a graph G is the smallest number of colors needed for a rainbow edge (vertex) coloring of G. In this article, we propose a very simple approach to studying rainbow connectivity in graphs. Using this idea, we give a unified proof of several known results, as well as some new ones.

Original languageEnglish
Pages (from-to)372-383
Number of pages12
JournalJournal of Graph Theory
Volume83
Issue number4
DOIs
Publication statusPublished - 1 Dec 2016
Externally publishedYes

Keywords

  • diameter
  • rainbow connectivity
  • random regular graphs

Cite this