Rainbow Connections of Graphs: A Survey

被引：191
作者：
Li, Xueliang [1 ,2 ]
Shi, Yongtang [1 ,2 ]
Sun, Yuefang [1 ,2 ]
机构：
[1] Nankai Univ, Ctr Combinator, Tianjin 300071, Peoples R China
[2] Nankai Univ, LPMC TJKLC, Tianjin 300071, Peoples R China
来源：
GRAPHS AND COMBINATORICS | 2013年 / 29卷 / 01期
关键词：
Rainbow path; (Strong) rainbow connection number; Rainbow k-connectivity; k-rainbow index; Rainbow vertex-connection number; Algorithm; Computational complexity; VERTEX-CONNECTION; K-CONNECTIVITY; COMPLEXITY; DIAMETER; NUMBERS;
D O I：
10.1007/s00373-012-1243-2
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
The concept of rainbow connection was introduced by Chartrand et al. [14] in 2008. It is interesting and recently quite a lot papers have been published about it. In this survey we attempt to bring together most of the results and papers that dealt with it. We begin with an introduction, and then try to organize the work into five categories, including (strong) rainbow connection number, rainbow k-connectivity, k-rainbow index, rainbow vertex-connection number, algorithms and computational complexity. This survey also contains some conjectures, open problems and questions.
引用
收藏
页码：1 / 38
页数：38
相关论文
共 83 条
  • [1] Ahadi A., 2010, ARXIV10013413V1MATHC
  • [2] THE ALGORITHMIC ASPECTS OF THE REGULARITY LEMMA
    ALON, N
    DUKE, RA
    LEFMANN, H
    RODL, V
    YUSTER, R
    [J]. JOURNAL OF ALGORITHMS, 1994, 16 (01) : 80 - 109
  • [3] Alon N., 2015, PROBABILISTIC METHOD
  • [4] Ananth P., 2011, ARXIV11042074V1CSCC
  • [5] [Anonymous], 2008, Chromatic Graph Theory
  • [6] [Anonymous], 2008, Graph Theory
  • [7] Basavaraju M., 2011, ARXIV11044190V1MATHC
  • [8] Basavaraju M., 2012, GRAPHS COMB IN PRESS
  • [9] An (O)over-tilda(n(3/14))-coloring algorithm for 3-colorable graphs
    Blum, A
    Karger, D
    [J]. INFORMATION PROCESSING LETTERS, 1997, 61 (01) : 49 - 53
  • [10] THRESHOLD FUNCTIONS
    BOLLOBAS, B
    THOMASON, A
    [J]. COMBINATORICA, 1987, 7 (01) : 35 - 38
123456789