{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,19]],"date-time":"2023-10-19T08:12:52Z","timestamp":1697703172842},"reference-count":17,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2009,4,6]],"date-time":"2009-04-06T00:00:00Z","timestamp":1238976000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Graph Theory"],"published-print":{"date-parts":[[2009,7]]},"abstract":"Abstract<\/jats:title>It was only recently shown by Shi and Wormald, using the differential equation method to analyze an appropriate algorithm, that a random 5\u2010regular graph asymptotically almost surely has chromatic number at most 4. Here, we show that the chromatic number of a random 5\u2010regular graph is asymptotically almost surely equal to 3, provided a certain four\u2010variable function has a unique maximum at a given point in a bounded domain. We also describe extensive numerical evidence that strongly suggests that the latter condition holds. The proof applies the small subgraph conditioning method to the number of locally rainbow balanced 3\u2010colorings, where a coloring is balanced<\/jats:italic> if the number of vertices of each color is equal, and locally rainbow<\/jats:italic> if every vertex is adjacent to at least one vertex of each of the other colors. \u00a9 2009 Wiley Periodicals, Inc. J Graph Theory 61: 157\u2013191, 2009<\/jats:p>","DOI":"10.1002\/jgt.20369","type":"journal-article","created":{"date-parts":[[2009,4,6]],"date-time":"2009-04-06T17:50:23Z","timestamp":1239040223000},"page":"157-191","source":"Crossref","is-referenced-by-count":4,"title":["On the chromatic number of a random 5\u2010regular graph"],"prefix":"10.1002","volume":"61","author":[{"given":"J.","family":"D\u00edaz","sequence":"first","affiliation":[]},{"given":"A. C.","family":"Kaporis","sequence":"additional","affiliation":[]},{"given":"G. D.","family":"Kemkes","sequence":"additional","affiliation":[]},{"given":"L. M.","family":"Kirousis","sequence":"additional","affiliation":[]},{"given":"X.","family":"P\u00e9rez","sequence":"additional","affiliation":[]},{"given":"N.","family":"Wormald","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2009,4,6]]},"reference":[{"key":"e_1_2_1_2_2","series-title":"Applied Math. Series","volume-title":"Handbook of Mathematical Functions","author":"Abramowitz M.","year":"1972"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00120-X"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27821-4_20"},{"key":"e_1_2_1_5_2","unstructured":"H.AssiyatunandN.Wormald Independent sets and 2\u2010independent sets in randomd\u2010regular graphs in preparation."},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(80)80030-8"},{"key":"e_1_2_1_7_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/11561071_21","volume-title":"Algorithms \u2010 ESA 2005","author":"D\u00edaz J.","year":"2005"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.70.046705"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.66.056126"},{"key":"e_1_2_1_11_2","unstructured":"M.Molloy The Chromatic Number of Sparse Random Graphs Master's Thesis University of Waterloo 1992."},{"key":"e_1_2_1_12_2","first-page":"1063","volume-title":"Handbook of Combinatorics","author":"Odlyzko A.","year":"1995"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030202"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240050209"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007693"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007954"},{"key":"e_1_2_1_17_2","series-title":"Computer Science and Scientific Computing","volume-title":"Asymptotic approximations of integrals","author":"Wong R.","year":"1989"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511721335.010"}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fjgt.20369","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.20369","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,18]],"date-time":"2023-10-18T21:34:23Z","timestamp":1697664863000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.20369"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,4,6]]},"references-count":17,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,7]]}},"alternative-id":["10.1002\/jgt.20369"],"URL":"https:\/\/doi.org\/10.1002\/jgt.20369","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"value":"0364-9024","type":"print"},{"value":"1097-0118","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,4,6]]}}}