Some Remarks on Rainbow Connectivity

Nina Kamčev; Michael Krivelevich; Benny Sudakov

doi:10.1016/j.endm.2015.06.019

Some Remarks on Rainbow Connectivity

Nina Kamčev, Michael Krivelevich, Benny Sudakov

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

Abstract

An edge- (vertex-) coloured 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 colours. Rainbow edge (vertex) connectivity of a graph G is the smallest number of colours needed for a rainbow edge (vertex) colouring of G. In this paper we propose a very simple approach to studying rainbow connectivity in graphs. Using this idea, we give a unified proof of several new and known results, focusing on random regular graphs.

Original language	English
Pages (from-to)	123-131
Number of pages	9
Journal	Electronic Notes in Discrete Mathematics
Volume	49
DOIs	https://doi.org/10.1016/j.endm.2015.06.019
Publication status	Published - 1 Nov 2015
Externally published	Yes

Keywords

Diameter
Rainbow connectivity
Random regular graph

Access to Document

10.1016/j.endm.2015.06.019

Cite this

@article{3064d8798f754b54b3cabf3849ac43f5,

title = "Some Remarks on Rainbow Connectivity",

abstract = "An edge- (vertex-) coloured 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 colours. Rainbow edge (vertex) connectivity of a graph G is the smallest number of colours needed for a rainbow edge (vertex) colouring of G. In this paper we propose a very simple approach to studying rainbow connectivity in graphs. Using this idea, we give a unified proof of several new and known results, focusing on random regular graphs.",

keywords = "Diameter, Rainbow connectivity, Random regular graph",

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

year = "2015",

month = nov,

day = "1",

doi = "10.1016/j.endm.2015.06.019",

language = "English",

volume = "49",

pages = "123--131",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier",

}

TY - JOUR

T1 - Some Remarks on Rainbow Connectivity

AU - Kamčev, Nina

AU - Krivelevich, Michael

AU - Sudakov, Benny

PY - 2015/11/1

Y1 - 2015/11/1

N2 - An edge- (vertex-) coloured 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 colours. Rainbow edge (vertex) connectivity of a graph G is the smallest number of colours needed for a rainbow edge (vertex) colouring of G. In this paper we propose a very simple approach to studying rainbow connectivity in graphs. Using this idea, we give a unified proof of several new and known results, focusing on random regular graphs.

AB - An edge- (vertex-) coloured 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 colours. Rainbow edge (vertex) connectivity of a graph G is the smallest number of colours needed for a rainbow edge (vertex) colouring of G. In this paper we propose a very simple approach to studying rainbow connectivity in graphs. Using this idea, we give a unified proof of several new and known results, focusing on random regular graphs.

KW - Diameter

KW - Rainbow connectivity

KW - Random regular graph

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

U2 - 10.1016/j.endm.2015.06.019

DO - 10.1016/j.endm.2015.06.019

M3 - Article

AN - SCOPUS:84947807661

VL - 49

SP - 123

EP - 131

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

SN - 1571-0653

ER -

Some Remarks on Rainbow Connectivity

Abstract

Keywords

Access to Document

Other files and links

Research output

Some Remarks on Rainbow Connectivity

Cite this