{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T18:51:03Z","timestamp":1777143063551,"version":"3.51.4"},"reference-count":84,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2012,10,16]],"date-time":"2012-10-16T00:00:00Z","timestamp":1350345600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2013,1]]},"DOI":"10.1007\/s00373-012-1243-2","type":"journal-article","created":{"date-parts":[[2012,10,17]],"date-time":"2012-10-17T18:59:38Z","timestamp":1350500378000},"page":"1-38","source":"Crossref","is-referenced-by-count":169,"title":["Rainbow Connections of Graphs: A Survey"],"prefix":"10.1007","volume":"29","author":[{"given":"Xueliang","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yongtang","family":"Shi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuefang","family":"Sun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,10,16]]},"reference":[{"key":"1243_CR1","unstructured":"Ahadi, A., Dehghan, A.: On rainbow connection of strongly regular graphs. arXiv:1001.3413v1 [math.CO] (2010)"},{"key":"1243_CR2","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1006\/jagm.1994.1005","volume":"6","author":"N. Alon","year":"1994","unstructured":"Alon N., Duke R., Lefmann H., R\u00f6dl V., Yuster R.: The algorithmic aspects of the Regularity Lemma. J. Algorithms 6, 80\u2013109 (1994)","journal-title":"J. Algorithms"},{"key":"1243_CR3","doi-asserted-by":"crossref","DOI":"10.1002\/0471722154","volume-title":"The Probabilistic Method","author":"N. Alon","year":"2000","unstructured":"Alon N., Spencer J.: The Probabilistic Method, 2nd edn. Wiley, New York (2000)","edition":"2"},{"key":"1243_CR4","unstructured":"Ananth, P., Nasre, M.: New hardness results in rainbow connectivity. arXiv:1104.2074v1 [cs.CC] (2011)"},{"key":"1243_CR5","doi-asserted-by":"crossref","unstructured":"Basavaraju, M., Chandran, L.S., Rajendraprasad, D., Ramaswamy, A.: Rainbow connection number and radius. Graphs Combin. (2012) (to appear)","DOI":"10.1007\/s00373-012-1267-7"},{"key":"1243_CR6","unstructured":"Basavaraju, M., Chandran, L.S., Rajendraprasad, D., Ramaswamy, A.: Rainbow connection number of graph power and graph products. arXiv:1104.4190v1 [math.CO] (2011)"},{"issue":"1","key":"1243_CR7","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/S0020-0190(96)00190-1","volume":"61","author":"A. Blum","year":"1997","unstructured":"Blum A., Karger D.: An \u00d5 (n 3\/14)-coloring algorithm for 3-colorable graphs. Inf. Process. Lett. 61(1), 49\u201353 (1997)","journal-title":"Inf. Process. Lett."},{"key":"1243_CR8","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/BF02579198","volume":"7","author":"B. Bollob\u00e1s","year":"1986","unstructured":"Bollob\u00e1s B., Thomason A.: Threshold functions. Combinatorica 7, 35\u201338 (1986)","journal-title":"Combinatorica"},{"key":"1243_CR9","doi-asserted-by":"crossref","unstructured":"Bondy, J.A., Murty, U.S.R.: Graph Theory. GTM 244, Springer, Berlin (2008)","DOI":"10.1007\/978-1-84628-970-5"},{"key":"1243_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1142\/S1793042105000108","volume":"1","author":"J. Bourgain","year":"2005","unstructured":"Bourgain J.: More on the sum-product phenomenon in prime fields and its applications. Int. J. Number Theory 1, 1\u201332 (2005)","journal-title":"Int. J. Number Theory"},{"key":"1243_CR11","doi-asserted-by":"crossref","first-page":"R57","DOI":"10.37236\/781","volume":"15","author":"Y. Caro","year":"2008","unstructured":"Caro Y., Lev A., Roditty Y., Tuza Z., Yuster R.: On rainbow connection. Electron. J. Combin. 15, R57 (2008)","journal-title":"Electron. J. Combin."},{"key":"1243_CR12","unstructured":"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\u2013254 (2009) (Also, see J. Combin. Optim. 21, 330\u2013347 (2011))"},{"key":"1243_CR13","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1002\/jgt.20643","volume":"71","author":"L.S. Chandran","year":"2012","unstructured":"Chandran L.S., Das A., Rajendraprasad D., Varma N.M.: Rainbow connection number and connected dominating sets. J. Graph Theory 71, 206\u2013218 (2012)","journal-title":"J. Graph Theory"},{"key":"1243_CR14","doi-asserted-by":"crossref","first-page":"85","DOI":"10.21136\/MB.2008.133947","volume":"133","author":"G. Chartrand","year":"2008","unstructured":"Chartrand G., Johns G.L., McKeon K.A., Zhang P.: Rainbow connection in graphs. Math. Bohem. 133, 85\u201398 (2008)","journal-title":"Math. Bohem."},{"key":"1243_CR15","doi-asserted-by":"crossref","unstructured":"Chandran, L.S., Rajendraprasad, D.: Rainbow colouring of split and threshold graphs COCOON. In: LNCS, vol. 7434, pp. 181\u2013192. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-32241-9_16"},{"key":"1243_CR16","first-page":"209","volume":"184","author":"G. Chartrand","year":"2007","unstructured":"Chartrand G., Johns G.L., McKeon K.A., Zhang P.: On the rainbow connectivity of cages. Congr. Numer. 184, 209\u2013222 (2007)","journal-title":"Congr. Numer."},{"issue":"2","key":"1243_CR17","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1002\/net.20296","volume":"54","author":"G. Chartrand","year":"2009","unstructured":"Chartrand G., Johns G.L., McKeon K.A., Zhang P.: The rainbow connectivity of a graph. Networks 54(2), 75\u201381 (2009)","journal-title":"Networks"},{"key":"1243_CR18","first-page":"360","volume":"55","author":"G. Chartrand","year":"2010","unstructured":"Chartrand G., Okamoto F., Zhang P.: Rainbow trees in graphs and generalized connectivity. Networks 55, 360\u2013367 (2010)","journal-title":"Networks"},{"key":"1243_CR19","doi-asserted-by":"crossref","unstructured":"Chartrand, G., Zhang, P.: Chromatic Graph Theory. Chapman & Hall, London (2008)","DOI":"10.1201\/9781584888017"},{"key":"1243_CR20","doi-asserted-by":"crossref","unstructured":"Chen, L., Li, X., Lian, H.: Nordhaus-Gaddum-type theorem for rainbow connection number of graphs. Graphs Combin. (2012) (in press)","DOI":"10.1007\/s00373-012-1183-x"},{"key":"1243_CR21","first-page":"335","volume":"86","author":"L. Chen","year":"2011","unstructured":"Chen L., Li X., Liu M.: Nordhaus-Gaddum-type theorem for the rainbow vertex-connection number of a graph. Util. Math. 86, 335\u2013340 (2011)","journal-title":"Util. Math."},{"key":"1243_CR22","doi-asserted-by":"crossref","first-page":"4531","DOI":"10.1016\/j.tcs.2011.04.032","volume":"412","author":"L. Chen","year":"2011","unstructured":"Chen L., Li X., Shi Y.: The complexity of determining the rainbow vertex-connection of graphs. Theoret. Comput. Sci. 412, 4531\u20134535 (2011)","journal-title":"Theoret. Comput. Sci."},{"key":"1243_CR23","first-page":"193","volume":"104","author":"X. Chen","year":"2012","unstructured":"Chen X., Li X.: A solution to a conjecture on the rainbow connection number. Ars Combin. 104, 193\u2013196 (2012)","journal-title":"Ars Combin."},{"issue":"3","key":"1243_CR24","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1137\/S0895480193250125","volume":"10","author":"D. Corneil","year":"1997","unstructured":"Corneil D., Olariu S., Stewart L.: Asteroidal triple-free graphs. SIAM J. Discrete Math. 10(3), 399\u2013430 (1997)","journal-title":"SIAM J. Discrete Math."},{"key":"1243_CR25","doi-asserted-by":"crossref","first-page":"774","DOI":"10.1016\/j.disc.2009.09.010","volume":"310","author":"D. Dellamonica Jr","year":"2010","unstructured":"Dellamonica D. Jr, Magnant C., Martin D.: Rainbow paths. Discrete Math. 310, 774\u2013781 (2010)","journal-title":"Discrete Math."},{"key":"1243_CR26","doi-asserted-by":"crossref","unstructured":"Dong, J., Li, X.: Upper bounds involving parameter \u03c32 for the rainbow connection. Acta Math. Appl. Sin. (2012) (to appear)","DOI":"10.1007\/s10255-013-0247-x"},{"key":"1243_CR27","doi-asserted-by":"crossref","unstructured":"Dong, J., Li, X.: Rainbow connection number, bridges and radius. Graphs Combin. (2012) (in press)","DOI":"10.1007\/s00373-012-1218-3"},{"key":"1243_CR28","doi-asserted-by":"crossref","unstructured":"Dong, J., Li, X.: Rainbow connection numbers and the minimum degree sum of a graph. Sci. China Ser. A (2012) (to appear)","DOI":"10.1360\/012012-120"},{"key":"1243_CR29","unstructured":"Dong, J., Li, X.: Sharp upper bound for the rainbow connection number of a graph with diameter 2. arXiv:1106.1258v3 [math.CO] (2011)"},{"key":"1243_CR30","unstructured":"Dong, J., Li, X.: On a question on graphs with rainbow connection number 2. arXiv:1109.5004v2 [math.CO] (2011)"},{"key":"1243_CR31","doi-asserted-by":"crossref","unstructured":"Ekstein, J., Holub, P., Kaiser, T., Kochy, M., Camachoy, S.M., Ryj\u00e1\u010dek, Z., Schiermeyer, I.: The rainbow connection number of 2-connected graphs. Discrete Math. (2012) (in press)","DOI":"10.1016\/j.disc.2012.04.022"},{"issue":"6","key":"1243_CR32","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1002\/net.3230220608","volume":"22","author":"E.S. Elmallah","year":"1992","unstructured":"Elmallah E.S., Colbourn C.J.: Series-parallel subgraphs of planar graphs. Networks 22(6), 607\u2013614 (1992)","journal-title":"Networks"},{"issue":"1","key":"1243_CR33","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0095-8956(89)90066-X","volume":"47","author":"P. Erd\u0151s","year":"1989","unstructured":"Erd\u0151s P., Pach J., Pollack R., Tuza Z.: Radius, diameter, and minimum degree. J. Combin. Theory, Ser. B. 47(1), 73\u201379 (1989)","journal-title":"J. Combin. Theory, Ser. B."},{"key":"1243_CR34","first-page":"17","volume":"5","author":"P. Erd\u0151s","year":"1960","unstructured":"Erd\u0151s P., R\u00e9nyi A.: On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutato Int. Kozl. 5, 17\u201361 (1960)","journal-title":"Magyar Tud. Akad. Mat. Kutato Int. Kozl."},{"key":"1243_CR35","unstructured":"Ericksen, A.: A matter of security. Graduating Engineer & Computer Careers, pp. 24\u201328 (2007)"},{"key":"1243_CR36","doi-asserted-by":"crossref","unstructured":"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\u2013589 (2007)","DOI":"10.1109\/FOCS.2007.12"},{"key":"1243_CR37","doi-asserted-by":"crossref","unstructured":"Frieze, A., Tsourakakis, C.E.: Rainbow connectivity of sparse random graphs. arXiv:1201.4603v2 [math.CO] (2012)","DOI":"10.1007\/978-3-642-32512-0_46"},{"key":"1243_CR38","doi-asserted-by":"crossref","first-page":"2993","DOI":"10.1090\/S0002-9939-96-03732-X","volume":"124","author":"E. Friedgut","year":"1996","unstructured":"Friedgut E., Kalai G.: Every monotone graph property has a sharp threshold. Proc. Am. Math. Soc. 124, 2993\u20133002 (1996)","journal-title":"Proc. Am. Math. Soc."},{"key":"1243_CR39","unstructured":"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\u00e9db\u0301b11, Electron. Notes Discrete Math. (to appear)"},{"key":"1243_CR40","unstructured":"Gologranca T., Meki\u0161 G., Peterin I.: Rainbow connection and graph products. IMFM Preprint Series 49,\u2013#1149 (2011)"},{"key":"1243_CR41","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/0898-1221(88)90213-1","volume":"15","author":"F. Harary","year":"1988","unstructured":"Harary F., Hayes J., Wu H.: A survey of the theory of hypercube graphs. Comput. Math. Appl. 15, 277\u2013289 (1988)","journal-title":"Comput. Math. Appl."},{"key":"1243_CR42","doi-asserted-by":"crossref","unstructured":"Klav\u0306ar, S., Mekis\u0306, G.: On the rainbow connection of Cartesian products and their subgraphs. Discuss. Math. Graph Theory (2012) (to appear)","DOI":"10.7151\/dmgt.1644"},{"issue":"10","key":"1243_CR43","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1016\/j.ipl.2012.01.014","volume":"112","author":"J. He","year":"2012","unstructured":"He J., Liang H.: On rainbow-k-connectivity of random graphs. Inf. Process. Lett. 112(10), 406\u2013410 (2012)","journal-title":"Inf. Process. Lett."},{"key":"1243_CR44","doi-asserted-by":"crossref","unstructured":"Hedetniemi, S.T., Slater, P.J.: Line graphs of triangleless graphs and iterated clique graphs. In: Alavi, Y. et\u00a0al. (eds.) Graph Theory and Applications. Lecture Notes in Mathematics, vol. 303, , pp. 139\u2013147. Springer, Berlin 1972; MR49#151","DOI":"10.1007\/BFb0067365"},{"key":"1243_CR45","unstructured":"Hemminger, R., Beineke, L.: Line graphs and line digraphs. In: Beineke, L. et\u00a0al. (eds.) Selected Topics in Graph Theory, pp. 271\u2013305. Academic Press, London (1978)"},{"key":"1243_CR46","unstructured":"Huang, X., Li, H., Li, X., Sun, Y.: Oriented diameter and rainbow connection number of a graph. arXiv:1111.3480v1 [math.CO] (2011)"},{"key":"1243_CR47","unstructured":"Huang, X., Li X., Shi, Y.: Rainbow connection for planar graphs and line graphs. arXiv:1110.3147 [cs.CC] (2011)"},{"key":"1243_CR48","volume-title":"Product Graphs\u2013Structure and Recognition","author":"W. Imrich","year":"2000","unstructured":"Imrich W., Klavzar S.: Product Graphs\u2013Structure and Recognition. Wiley, New York (2000)"},{"key":"1243_CR49","unstructured":"Johns, G.L., Okamoto, F., Zhang, P.: The rainbow connectivities of small cubic graphs. Ars Combin. (2012) (to appear)"},{"key":"1243_CR50","doi-asserted-by":"crossref","first-page":"313","DOI":"10.7151\/dmgt.1547","volume":"31","author":"A. Kemnitz","year":"2011","unstructured":"Kemnitz A., Schiermeyer I.: Graphs with rainbow connection number two. Discuss. Math. Graph Theory 31, 313\u2013320 (2011)","journal-title":"Discuss. Math. Graph Theory"},{"key":"1243_CR51","doi-asserted-by":"crossref","unstructured":"Kemnitz, A., Przybylo, J., Schiermeyer I., Wozniak, M.: Rainbow connection in sparse graphs. Discuss. Math. Graph Theory (2012) (to appear)","DOI":"10.7151\/dmgt.1640"},{"key":"1243_CR52","unstructured":"Koml\u00f3s, J., Simonovits, M.: Szemer\u00e9di\u2019s Regularity Lemma and its applications in graph theory. In: Mikl\u00f3s, D., S\u00f3s, V.T., Sz\u00f6nyi, T. (eds.) Combinatorics, Paul Erd\u0151 is Eighty, vol. 2, pp. 295\u2013352. Bolyai Society Mathematical Studies, Budapest (1996)"},{"issue":"3","key":"1243_CR53","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1002\/jgt.20418","volume":"63","author":"M. Krivelevich","year":"2009","unstructured":"Krivelevich M., Yuster R.: The rainbow connection of a graph is (at most) reciprocal to its minimum degree. J. Graph Theory 63(3), 185\u2013191 (2009)","journal-title":"J. Graph Theory"},{"key":"1243_CR54","unstructured":"Le, V., Tuza, Z.: Finding optimal rainbow connection is hard. Preprint (2009)"},{"issue":"11","key":"1243_CR55","doi-asserted-by":"crossref","first-page":"4082","DOI":"10.1016\/j.camwa.2011.09.056","volume":"62","author":"H. Li","year":"2011","unstructured":"Li H., Li X., Liu S.: The (strong) rainbow connection numbers of Cayley graphs on Abelian groups. Comput. Math. Appl. 62(11), 4082\u20134088 (2011)","journal-title":"Comput. Math. Appl."},{"issue":"8","key":"1243_CR56","doi-asserted-by":"crossref","first-page":"1453","DOI":"10.1016\/j.disc.2012.01.009","volume":"312","author":"H. Li","year":"2012","unstructured":"Li H., Li X., Liu S.: Rainbow connection in graphs with diameter 2. Discrete Math. 312(8), 1453\u20131457 (2012)","journal-title":"Discrete Math."},{"key":"1243_CR57","unstructured":"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)"},{"key":"1243_CR58","unstructured":"Li, S., Li, X.: Note on the complexity of deciding the rainbow connectedness for bipartite graphs. arXiv:1109.5534v2 [cs.CC] (2011)"},{"key":"1243_CR59","doi-asserted-by":"crossref","unstructured":"Li, X., Liu, M., Schiermeyer, I.: Rainbow connection number of dense graphs. Discuss. Math. Graph Theory (2012) (to appear)","DOI":"10.7151\/dmgt.1692"},{"key":"1243_CR60","unstructured":"Li, X., Liu, S.: Sharp upper bound for the rainbow connection numbers of 2-connected graphs. arXiv:1105.4210v2 [math.CO] (2011)"},{"key":"1243_CR61","doi-asserted-by":"crossref","unstructured":"Li, X., Liu, S.: Rainbow vertex-connection number of 2-connected graphs. arXiv:1110.5770 [math.CO] (2011)","DOI":"10.1007\/978-1-4614-3119-0_8"},{"key":"1243_CR62","unstructured":"Li, X., Liu, S.: A sharp upper bound for the rainbow 2-connection number of 2-connected graphs. arXiv:1204.0392 [math.CO] (2011)"},{"key":"1243_CR63","doi-asserted-by":"crossref","first-page":"P20","DOI":"10.37236\/1172","volume":"19","author":"X. Li","year":"2012","unstructured":"Li X., Liu S., Chandran L.S., Mathew R., Rajendraprasad D.: Rainbow connection number and connectivity. Electron. J. Combin. 19, P20 (2012)","journal-title":"Electron. J. Combin."},{"key":"1243_CR64","doi-asserted-by":"crossref","unstructured":"Li, X., Mao, Y., Shi, Y.: The strong rainbow vertex-connection of graphs. arXiv:1201.1541 [math.CO] (2011)","DOI":"10.1007\/978-1-4614-3119-0_8"},{"key":"1243_CR65","doi-asserted-by":"crossref","unstructured":"Li, X., Shi, Y.: On the rainbow vertex-connection. Discuss. Math. Graph Theory (2012) (to appear)","DOI":"10.7151\/dmgt.1664"},{"key":"1243_CR66","doi-asserted-by":"crossref","unstructured":"Li, X., Shi, Y.: Rainbow connection in 3-connected graphs. Graphs Combin. (2012) (in press)","DOI":"10.1007\/s00373-012-1204-9"},{"key":"1243_CR67","first-page":"449","volume":"100","author":"X. Li","year":"2011","unstructured":"Li X., Sun Y.: Rainbow connection numbers of line graphs. Ars Combin. 100, 449\u2013463 (2011)","journal-title":"Ars Combin."},{"issue":"2","key":"1243_CR68","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/s00373-011-1034-1","volume":"28","author":"X. Li","year":"2012","unstructured":"Li X., Sun Y: Upper bounds for the rainbow connection numbers of line graphs. Graphs Combin 28(2), 251\u2013263 (2012)","journal-title":"Graphs Combin"},{"key":"1243_CR69","first-page":"217","volume":"49","author":"X. Li","year":"2011","unstructured":"Li X., Sun Y.: On the rainbow k-connectivity of complete graphs. Australasian J. Combin. 49, 217\u2013226 (2011)","journal-title":"Australasian J. Combin."},{"key":"1243_CR70","first-page":"513","volume":"101","author":"X. Li","year":"2011","unstructured":"Li X., Sun Y.: Note on the rainbow k-connectivity of regular complete bipartite graphs. Ars Combin. 101, 513\u2013518 (2011)","journal-title":"Ars Combin."},{"key":"1243_CR71","doi-asserted-by":"crossref","unstructured":"Li, X., Sun, Y.: Characterize graphs with rainbow connection number m \u2013 2 and rainbow connection numbers of some graph operations. Preprint (2010)","DOI":"10.1007\/s00373-011-1034-1"},{"key":"1243_CR72","doi-asserted-by":"crossref","unstructured":"Li, X., Sun, Y.: On the strong rainbow connection number. Bull. Malays. Math. Sci. Soc. (2012) (in press)","DOI":"10.1007\/978-1-4614-3119-0_8"},{"key":"1243_CR73","first-page":"23","volume":"86","author":"X. Li","year":"2011","unstructured":"Li X., Sun Y.: Rainbow connection numbers of complementary graphs. Util. Math. 86, 23\u201331 (2011)","journal-title":"Util. Math."},{"key":"1243_CR74","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4614-3119-0","volume-title":"Rainbow Connections of Graphs, Springer Briefs in Mathematics","author":"X. Li","year":"2012","unstructured":"Li X., Sun Y.: Rainbow Connections of Graphs, Springer Briefs in Mathematics. Springer, New York (2012)"},{"key":"1243_CR75","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/BF01304873","volume":"23","author":"W. Mader","year":"1972","unstructured":"Mader W.: Ecken vom Grad n in minimalen n-fach zusammenhangenden Graphen. Arch. Math. 23, 219\u2013224 (1972)","journal-title":"Arch. Math."},{"key":"1243_CR76","doi-asserted-by":"crossref","first-page":"175","DOI":"10.2307\/2306658","volume":"63","author":"E.A. Nordhaus","year":"1956","unstructured":"Nordhaus E.A., Gaddum J.W.: On complementary graphs. Am. Math. Monthly 63, 175\u2013177 (1956)","journal-title":"Am. Math. Monthly"},{"key":"1243_CR77","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/S0304-3975(00)00176-6","volume":"244","author":"J.H. Park","year":"2000","unstructured":"Park J.H., Chwa K.Y.: Recursive circulants and their embeddings among hypercubes. Theoret. Comput. Sci. 244, 35\u201362 (2000)","journal-title":"Theoret. Comput. Sci."},{"key":"1243_CR78","unstructured":"Rao, A.: An exposition of Bourgain\u2019s 2-source extractor. in: ECCCTR: Electronic Colloquium on Computational Complexity, Technical Reports (2007)"},{"key":"1243_CR79","unstructured":"Rotman, J.J.: An Introduction to the Theory of Groups, GTM 148, Springer, Berlin (1994)"},{"key":"1243_CR80","doi-asserted-by":"crossref","unstructured":"Schiermeyer, I.: Rainbow connection in graphs with minimum degree three. IWOCA 2009. In: LNCS, vol. 5874, pp. 432\u2013437 (2009) (also see Discrete Appl. Math. (in press))","DOI":"10.1007\/978-3-642-10217-2_42"},{"key":"1243_CR81","unstructured":"Shaltiel, R.: Recent developments in explicit constructions of extractors. Bull. EATCS, 67\u201395 (2002)"},{"key":"1243_CR82","doi-asserted-by":"crossref","unstructured":"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\u201397. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-22685-4_8"},{"key":"1243_CR83","doi-asserted-by":"crossref","first-page":"150","DOI":"10.2307\/2371086","volume":"54","author":"H. Whitney","year":"1932","unstructured":"Whitney H.: Congruent graphs and the connectivity of graphs. Am. J. Math. 54, 150\u2013168 (1932)","journal-title":"Am. J. Math."},{"issue":"3","key":"1243_CR84","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1137\/0603036","volume":"3","author":"M. Yannakakis","year":"1982","unstructured":"Yannakakis M.: The complexity of the partial order dimension problem. SIAM J. Alg. Discrete Methods 3(3), 351\u2013358 (1982)","journal-title":"SIAM J. Alg. Discrete Methods"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-012-1243-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00373-012-1243-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-012-1243-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,30]],"date-time":"2024-04-30T10:19:48Z","timestamp":1714472388000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00373-012-1243-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,10,16]]},"references-count":84,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["1243"],"URL":"https:\/\/doi.org\/10.1007\/s00373-012-1243-2","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,10,16]]}}}