Some Remarks on Rainbow Connectivity

Nina Kamčev; Michael Krivelevich; Benny Sudakov

doi:10.1002/jgt.22003

Some Remarks on Rainbow Connectivity

Nina Kamčev, Michael Krivelevich, Benny Sudakov

Research output: Contribution to journal › Article › Research › peer-review

14 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 language	English
Pages (from-to)	372-383
Number of pages	12
Journal	Journal of Graph Theory
Volume	83
Issue number	4
DOIs	https://doi.org/10.1002/jgt.22003
Publication status	Published - 1 Dec 2016
Externally published	Yes

Keywords

diameter
rainbow connectivity
random regular graphs

Access to Document

10.1002/jgt.22003

Cite this

@article{001418fc21c9469991d36a4f272c61d1,

title = "Some Remarks on Rainbow Connectivity",

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.",

keywords = "diameter, rainbow connectivity, random regular graphs",

author = "Nina Kam{\v c}ev and Michael Krivelevich and Benny Sudakov",

year = "2016",

month = dec,

day = "1",

doi = "10.1002/jgt.22003",

language = "English",

volume = "83",

pages = "372--383",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "John Wiley \& Sons",

number = "4",

}

TY - JOUR

T1 - Some Remarks on Rainbow Connectivity

AU - Kamčev, Nina

AU - Krivelevich, Michael

AU - Sudakov, Benny

PY - 2016/12/1

Y1 - 2016/12/1

N2 - 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.

AB - 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.

KW - diameter

KW - rainbow connectivity

KW - random regular graphs

UR - http://www.scopus.com/inward/record.url?scp=84991711010&partnerID=8YFLogxK

U2 - 10.1002/jgt.22003

DO - 10.1002/jgt.22003

M3 - Article

AN - SCOPUS:84991711010

SN - 0364-9024

VL - 83

SP - 372

EP - 383

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 4

ER -

Some Remarks on Rainbow Connectivity

Abstract

Keywords

Access to Document

Other files and links

Research output

Some Remarks on Rainbow Connectivity

Cite this