×

Rainbow connections of graphs: a survey. (English) Zbl 1258.05058

Summary: The concept of rainbow connection was introduced by G. Chartrand et al. [Math. Bohem. 133, No. 1, 85–98 (2008; Zbl 1199.05106)]. 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.

MSC:

05C40 Connectivity
05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
05D40 Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science

Citations:

Zbl 1199.05106
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ahadi, A., Dehghan, A.: On rainbow connection of strongly regular graphs. arXiv:1001.3413v1 [math.CO] (2010)
[2] Alon N., Duke R., Lefmann H., Rödl V., Yuster R.: The algorithmic aspects of the Regularity Lemma. J. Algorithms 6, 80–109 (1994) · Zbl 0794.05119 · doi:10.1006/jagm.1994.1005
[3] Alon N., Spencer J.: The Probabilistic Method, 2nd edn. Wiley, New York (2000) · Zbl 0996.05001
[4] Ananth, P., Nasre, M.: New hardness results in rainbow connectivity. arXiv:1104.2074v1 [cs.CC] (2011)
[5] Basavaraju, M., Chandran, L.S., Rajendraprasad, D., Ramaswamy, A.: Rainbow connection number and radius. Graphs Combin. (2012) (to appear) · Zbl 1298.05103
[6] Basavaraju, M., Chandran, L.S., Rajendraprasad, D., Ramaswamy, A.: Rainbow connection number of graph power and graph products. arXiv:1104.4190v1 [math.CO] (2011) · Zbl 1306.05203
[7] Blum A., Karger D.: An Õ (n 3/14)-coloring algorithm for 3-colorable graphs. Inf. Process. Lett. 61(1), 49–53 (1997) · Zbl 1337.05096 · doi:10.1016/S0020-0190(96)00190-1
[8] Bollobás B., Thomason A.: Threshold functions. Combinatorica 7, 35–38 (1986) · Zbl 0648.05048 · doi:10.1007/BF02579198
[9] Bondy, J.A., Murty, U.S.R.: Graph Theory. GTM 244, Springer, Berlin (2008) · Zbl 1134.05001
[10] Bourgain J.: More on the sum-product phenomenon in prime fields and its applications. Int. J. Number Theory 1, 1–32 (2005) · Zbl 1173.11310 · doi:10.1142/S1793042105000108
[11] Caro Y., Lev A., Roditty Y., Tuza Z., Yuster R.: On rainbow connection. Electron. J. Combin. 15, R57 (2008) · Zbl 1181.05037
[12] Chakraborty, S., Fischer, E., Matsliah, A., Yuster, R.: Hardness and algorithms for rainbow connectivity. In: 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, pp. 243–254 (2009) (Also, see J. Combin. Optim. 21, 330–347 (2011)) · Zbl 1236.68080
[13] Chandran L.S., Das A., Rajendraprasad D., Varma N.M.: Rainbow connection number and connected dominating sets. J. Graph Theory 71, 206–218 (2012) · Zbl 1248.05098 · doi:10.1002/jgt.20643
[14] Chartrand G., Johns G.L., McKeon K.A., Zhang P.: Rainbow connection in graphs. Math. Bohem. 133, 85–98 (2008) · Zbl 1199.05106
[15] Chandran, L.S., Rajendraprasad, D.: Rainbow colouring of split and threshold graphs COCOON. In: LNCS, vol. 7434, pp. 181–192. Springer, Berlin (2012) · Zbl 1364.68223
[16] Chartrand G., Johns G.L., McKeon K.A., Zhang P.: On the rainbow connectivity of cages. Congr. Numer. 184, 209–222 (2007) · Zbl 1138.05042
[17] Chartrand G., Johns G.L., McKeon K.A., Zhang P.: The rainbow connectivity of a graph. Networks 54(2), 75–81 (2009) · Zbl 1205.05124 · doi:10.1002/net.20296
[18] Chartrand G., Okamoto F., Zhang P.: Rainbow trees in graphs and generalized connectivity. Networks 55, 360–367 (2010) · Zbl 1205.05085
[19] Chartrand, G., Zhang, P.: Chromatic Graph Theory. Chapman & Hall, London (2008) · Zbl 1169.05001
[20] Chen, L., Li, X., Lian, H.: Nordhaus-Gaddum-type theorem for rainbow connection number of graphs. Graphs Combin. (2012) (in press) · Zbl 1272.05044
[21] Chen L., Li X., Liu M.: Nordhaus-Gaddum-type theorem for the rainbow vertex-connection number of a graph. Util. Math. 86, 335–340 (2011) · Zbl 1264.05048
[22] Chen L., Li X., Shi Y.: The complexity of determining the rainbow vertex-connection of graphs. Theoret. Comput. Sci. 412, 4531–4535 (2011) · Zbl 1223.68079 · doi:10.1016/j.tcs.2011.04.032
[23] Chen X., Li X.: A solution to a conjecture on the rainbow connection number. Ars Combin. 104, 193–196 (2012) · Zbl 1274.05151
[24] Corneil D., Olariu S., Stewart L.: Asteroidal triple-free graphs. SIAM J. Discrete Math. 10(3), 399–430 (1997) · Zbl 0884.05075 · doi:10.1137/S0895480193250125
[25] Dellamonica D. Jr, Magnant C., Martin D.: Rainbow paths. Discrete Math. 310, 774–781 (2010) · Zbl 1209.05128 · doi:10.1016/j.disc.2009.09.010
[26] Dong, J., Li, X.: Upper bounds involving parameter {\(\sigma\)}2 for the rainbow connection. Acta Math. Appl. Sin. (2012) (to appear)
[27] Dong, J., Li, X.: Rainbow connection number, bridges and radius. Graphs Combin. (2012) (in press) · Zbl 1296.05069
[28] Dong, J., Li, X.: Rainbow connection numbers and the minimum degree sum of a graph. Sci. China Ser. A (2012) (to appear)
[29] Dong, J., Li, X.: Sharp upper bound for the rainbow connection number of a graph with diameter 2. arXiv:1106.1258v3 [math.CO] (2011)
[30] Dong, J., Li, X.: On a question on graphs with rainbow connection number 2. arXiv:1109.5004v2 [math.CO] (2011)
[31] Ekstein, J., Holub, P., Kaiser, T., Kochy, M., Camachoy, S.M., Ryjáček, Z., Schiermeyer, I.: The rainbow connection number of 2-connected graphs. Discrete Math. (2012) (in press)
[32] Elmallah E.S., Colbourn C.J.: Series-parallel subgraphs of planar graphs. Networks 22(6), 607–614 (1992) · Zbl 0766.05051 · doi:10.1002/net.3230220608
[33] Erdos P., Pach J., Pollack R., Tuza Z.: Radius, diameter, and minimum degree. J. Combin. Theory, Ser. B. 47(1), 73–79 (1989) · Zbl 0686.05029 · doi:10.1016/0095-8956(89)90066-X
[34] Erdos P., Rényi A.: On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutato Int. Kozl. 5, 17–61 (1960)
[35] Ericksen, A.: A matter of security. Graduating Engineer & Computer Careers, pp. 24–28 (2007)
[36] Fischer, E., Matsliah, A., Shapira, A.: Approximate hypergraph partitioning and applications. In: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 579–589 (2007) · Zbl 1271.68113
[37] Frieze, A., Tsourakakis, C.E.: Rainbow connectivity of sparse random graphs. arXiv:1201.4603v2 [math.CO] (2012) · Zbl 1372.05200
[38] Friedgut E., Kalai G.: Every monotone graph property has a sharp threshold. Proc. Am. Math. Soc. 124, 2993–3002 (1996) · Zbl 0864.05078 · doi:10.1090/S0002-9939-96-03732-X
[39] Fujita, S., Liu, H., Magnant, C.: Rainbow k-connection in dense graphs. preprint. Available at http://www.cantab.net/users/henry.liu/maths.htm . Extended abstract in Proceedings of Euro- Combédbb11, Electron. Notes Discrete Math. (to appear) · Zbl 1320.05040
[40] Gologranca T., Mekiš G., Peterin I.: Rainbow connection and graph products. IMFM Preprint Series 49,–#1149 (2011)
[41] Harary F., Hayes J., Wu H.: A survey of the theory of hypercube graphs. Comput. Math. Appl. 15, 277–289 (1988) · Zbl 0645.05061 · doi:10.1016/0898-1221(88)90213-1
[42] Klavar, S., Mekis, G.: On the rainbow connection of Cartesian products and their subgraphs. Discuss. Math. Graph Theory (2012) (to appear)
[43] He J., Liang H.: On rainbow-k-connectivity of random graphs. Inf. Process. Lett. 112(10), 406–410 (2012) · Zbl 1243.05218 · doi:10.1016/j.ipl.2012.01.014
[44] Hedetniemi, S.T., Slater, P.J.: Line graphs of triangleless graphs and iterated clique graphs. In: Alavi, Y. et al. (eds.) Graph Theory and Applications. Lecture Notes in Mathematics, vol. 303, , pp. 139–147. Springer, Berlin 1972; MR49#151 · Zbl 0255.05121
[45] Hemminger, R., Beineke, L.: Line graphs and line digraphs. In: Beineke, L. et al. (eds.) Selected Topics in Graph Theory, pp. 271–305. Academic Press, London (1978) · Zbl 0434.05056
[46] Huang, X., Li, H., Li, X., Sun, Y.: Oriented diameter and rainbow connection number of a graph. arXiv:1111.3480v1 [math.CO] (2011) · Zbl 1294.05104
[47] Huang, X., Li X., Shi, Y.: Rainbow connection for planar graphs and line graphs. arXiv:1110.3147 [cs.CC] (2011)
[48] Imrich W., Klavzar S.: Product Graphs–Structure and Recognition. Wiley, New York (2000)
[49] Johns, G.L., Okamoto, F., Zhang, P.: The rainbow connectivities of small cubic graphs. Ars Combin. (2012) (to appear) · Zbl 1274.05166
[50] Kemnitz A., Schiermeyer I.: Graphs with rainbow connection number two. Discuss. Math. Graph Theory 31, 313–320 (2011) · Zbl 1234.05092 · doi:10.7151/dmgt.1547
[51] Kemnitz, A., Przybylo, J., Schiermeyer I., Wozniak, M.: Rainbow connection in sparse graphs. Discuss. Math. Graph Theory (2012) (to appear)
[52] Komlós, J., Simonovits, M.: Szemerédi’s Regularity Lemma and its applications in graph theory. In: Miklós, D., Sós, V.T., Szönyi, T. (eds.) Combinatorics, Paul Erdo is Eighty, vol. 2, pp. 295–352. Bolyai Society Mathematical Studies, Budapest (1996) · Zbl 0851.05065
[53] Krivelevich M., Yuster R.: The rainbow connection of a graph is (at most) reciprocal to its minimum degree. J. Graph Theory 63(3), 185–191 (2009) · Zbl 1193.05079
[54] Le, V., Tuza, Z.: Finding optimal rainbow connection is hard. Preprint (2009)
[55] Li H., Li X., Liu S.: The (strong) rainbow connection numbers of Cayley graphs on Abelian groups. Comput. Math. Appl. 62(11), 4082–4088 (2011) · Zbl 1235.05063 · doi:10.1016/j.camwa.2011.09.056
[56] Li H., Li X., Liu S.: Rainbow connection in graphs with diameter 2. Discrete Math. 312(8), 1453–1457 (2012) · Zbl 1237.05118 · doi:10.1016/j.disc.2012.01.009
[57] Li, H., Li, X., Sun, Y.: Upper bound for the rainbow connection number of bridgeless graphs with diameter 3. arXiv:1109.2769v1 [math.CO] (2011)
[58] Li, S., Li, X.: Note on the complexity of deciding the rainbow connectedness for bipartite graphs. arXiv:1109.5534v2 [cs.CC] (2011)
[59] Li, X., Liu, M., Schiermeyer, I.: Rainbow connection number of dense graphs. Discuss. Math. Graph Theory (2012) (to appear) · Zbl 1275.05022
[60] Li, X., Liu, S.: Sharp upper bound for the rainbow connection numbers of 2-connected graphs. arXiv:1105.4210v2 [math.CO] (2011)
[61] Li, X., Liu, S.: Rainbow vertex-connection number of 2-connected graphs. arXiv:1110.5770 [math.CO] (2011)
[62] Li, X., Liu, S.: A sharp upper bound for the rainbow 2-connection number of 2-connected graphs. arXiv:1204.0392 [math.CO] (2011)
[63] Li X., Liu S., Chandran L.S., Mathew R., Rajendraprasad D.: Rainbow connection number and connectivity. Electron. J. Combin. 19, P20 (2012) · Zbl 1243.05133
[64] Li, X., Mao, Y., Shi, Y.: The strong rainbow vertex-connection of graphs. arXiv:1201.1541 [math.CO] (2011) · Zbl 1293.05115
[65] Li, X., Shi, Y.: On the rainbow vertex-connection. Discuss. Math. Graph Theory (2012) (to appear) · Zbl 1293.05116
[66] Li, X., Shi, Y.: Rainbow connection in 3-connected graphs. Graphs Combin. (2012) (in press) · Zbl 1272.05053
[67] Li X., Sun Y.: Rainbow connection numbers of line graphs. Ars Combin. 100, 449–463 (2011) · Zbl 1265.05237
[68] Li X., Sun Y: Upper bounds for the rainbow connection numbers of line graphs. Graphs Combin 28(2), 251–263 (2012) · Zbl 1256.05073 · doi:10.1007/s00373-011-1034-1
[69] Li X., Sun Y.: On the rainbow k-connectivity of complete graphs. Australasian J. Combin. 49, 217–226 (2011) · Zbl 1228.05196
[70] Li X., Sun Y.: Note on the rainbow k-connectivity of regular complete bipartite graphs. Ars Combin. 101, 513–518 (2011) · Zbl 1265.05236
[71] Li, X., Sun, Y.: Characterize graphs with rainbow connection number m – 2 and rainbow connection numbers of some graph operations. Preprint (2010)
[72] Li, X., Sun, Y.: On the strong rainbow connection number. Bull. Malays. Math. Sci. Soc. (2012) (in press)
[73] Li X., Sun Y.: Rainbow connection numbers of complementary graphs. Util. Math. 86, 23–31 (2011) · Zbl 1264.05052
[74] Li X., Sun Y.: Rainbow Connections of Graphs, Springer Briefs in Mathematics. Springer, New York (2012) · Zbl 1250.05066
[75] Mader W.: Ecken vom Grad n in minimalen n-fach zusammenhangenden Graphen. Arch. Math. 23, 219–224 (1972) · Zbl 0233.05119 · doi:10.1007/BF01304873
[76] Nordhaus E.A., Gaddum J.W.: On complementary graphs. Am. Math. Monthly 63, 175–177 (1956) · Zbl 0070.18503 · doi:10.2307/2306658
[77] Park J.H., Chwa K.Y.: Recursive circulants and their embeddings among hypercubes. Theoret. Comput. Sci. 244, 35–62 (2000) · Zbl 0945.68003 · doi:10.1016/S0304-3975(00)00176-6
[78] Rao, A.: An exposition of Bourgain’s 2-source extractor. in: ECCCTR: Electronic Colloquium on Computational Complexity, Technical Reports (2007)
[79] Rotman, J.J.: An Introduction to the Theory of Groups, GTM 148, Springer, Berlin (1994)
[80] Schiermeyer, I.: Rainbow connection in graphs with minimum degree three. IWOCA 2009. In: LNCS, vol. 5874, pp. 432–437 (2009) (also see Discrete Appl. Math. (in press)) · Zbl 1267.05125
[81] Shaltiel, R.: Recent developments in explicit constructions of extractors. Bull. EATCS, 67–95 (2002) · Zbl 1051.68070
[82] Uchizawa, K., Aoki, T., Ito, T., Suzuki, A., Zhou, X.: On the rainbow connectivity of graphs: complexity and FPT algorithms. In: COCOON 2011, LNCS, vol. 6842, pp. 86–97. Springer, Berlin (2011) · Zbl 1334.68107
[83] Whitney H.: Congruent graphs and the connectivity of graphs. Am. J. Math. 54, 150–168 (1932) · JFM 58.0609.01 · doi:10.2307/2371086
[84] Yannakakis M.: The complexity of the partial order dimension problem. SIAM J. Alg. Discrete Methods 3(3), 351–358 (1982) · Zbl 0516.06001 · doi:10.1137/0603036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.