{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T01:56:20Z","timestamp":1787363780983,"version":"build-2736575974"},"reference-count":17,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>An edge colored graph $G$ is rainbow edge connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection of a connected graph $G$, denoted by $rc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow connected. In this work we study the rainbow connection of the random $r$-regular graph $G=G(n,r)$ of order $n$, where $r\\ge 4$ is a constant. We prove that with probability tending to one as $n$ goes to infinity the rainbow connection of $G$ satisfies $rc(G)=O(\\log n)$, which is best possible up to a hidden constant.<\/jats:p>","DOI":"10.1137\/140998433","type":"journal-article","created":{"date-parts":[[2015,11,17]],"date-time":"2015-11-17T11:26:32Z","timestamp":1447759592000},"page":"2255-2266","source":"Crossref","is-referenced-by-count":13,"title":["Rainbow Connection of Random Regular Graphs"],"prefix":"10.1137","volume":"29","author":[{"given":"Andrzej","family":"Dudek","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alan M.","family":"Frieze","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Charalampos E.","family":"Tsourakakis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,11,17]]},"reference":[{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-012-1267-7"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(80)80030-8"},{"key":"atypb4","unstructured":"B. Bolloba\u0301s,\n                      Random graphs\n                      , 2nd ed., Cambridge Stud. Adv. Math. 73, Cambridge University Press, Cambridge, 2001."},{"key":"atypb5","doi-asserted-by":"crossref","first-page":"R57","DOI":"10.37236\/781","volume":"15","author":"Caro Y.","year":"2008","journal-title":"Electron. J. Combin."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-009-9250-9"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20643"},{"key":"atypb8","doi-asserted-by":"crossref","first-page":"85","DOI":"10.21136\/MB.2008.133947","volume":"133","author":"Chartrand G.","year":"2008","journal-title":"Math. Bohem."},{"key":"atypb9","unstructured":"A. Dudek, A. Frieze, A. Rucin\u0301ski, and M. S\u030cileikis,\n                      Embedding the Erdo\u0308s-Re\u0301nyi Hypergraph Into the Tandom Regular Hypergraph and Hamiltonicity\n                      , preprint, arXiv:1508.06677, 2015."},{"key":"atypb10","first-page":"541","author":"Frieze A.","year":"2012","journal-title":"Heidelberg"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2012.01.014"},{"key":"atypb12","doi-asserted-by":"crossref","first-page":"P37","DOI":"10.37236\/2708","volume":"19","author":"Heckel A.","year":"2012","journal-title":"Electron. J. Combin."},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"S. Janson, T. \u0141uczak, and A. Rucin\u0301ski,\n                      Random graphs\n                      , Wiley Ser. Discrete Math. Optim., Wiley-Interscience, New York, 2000.","DOI":"10.1002\/9781118032718"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"N. Kamc\u030cev, M. Krivelevich, and B. Sudakov,\n                      Some Remarks on Rainbow Connectivity\n                      , preprint, arXiv:1501.00821, 2015.","DOI":"10.1016\/j.endm.2015.06.019"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2003.10.007"},{"key":"atypb16","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1002\/jgt.20418","volume":"63","author":"Krivelevich M.","year":"2010","journal-title":"J. Graph Theory"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-012-1243-2"},{"key":"atypb18","first-page":"239","author":"Wormald N. C.","year":"1999","journal-title":"Cambridge"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/140998433","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:47:37Z","timestamp":1787320057000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/140998433"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/140998433"],"URL":"https:\/\/doi.org\/10.1137\/140998433","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}