{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,22]],"date-time":"2025-06-22T04:03:00Z","timestamp":1750564980196,"version":"3.41.0"},"reference-count":18,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2007,9,1]],"date-time":"2007-09-01T00:00:00Z","timestamp":1188604800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2007,9]]},"abstract":"Let d<\/jats:bold>=1\u2264d<\/jats:italic>1<\/jats:sub>\u2264 d<\/jats:italic>2<\/jats:sub>\u2264\u00b7\u00b7\u00b7.\u2264 d<\/jats:italic>\n\t n<\/jats:italic>\n\t <\/jats:sub> be a non-decreasing sequence of n<\/jats:italic> positive integers, whose sum is even. Let \n\t $\\mathbb G_{n,{\\bf d}$<\/jats:alt-text>\n\t <\/jats:inline-graphic> denote the set of graphs with vertex set [n<\/jats:italic>]={1,2,.\u00a0.\u00a0.., n<\/jats:italic>} in which the degree of vertex i<\/jats:italic> is d<\/jats:italic>\n\t i<\/jats:italic>\n\t <\/jats:sub>. Let G<\/jats:italic>n<\/jats:italic>,d<\/jats:bold><\/jats:sub> be chosen uniformly at random from \n\t $\\mathbb G_{n,{\\bf d}$<\/jats:alt-text>\n\t <\/jats:inline-graphic>. Let d<\/jats:italic>=(d<\/jats:italic>1<\/jats:sub>+d<\/jats:italic>2<\/jats:sub>+\u00b7\u00b7\u00b7.+d<\/jats:italic>\n\t n<\/jats:italic>\n\t <\/jats:sub>)\/n<\/jats:italic> be the average degree. We give a condition on d<\/jats:bold> under which we can show that w.h.p. the chromatic number of \n\t $\\mathbb G_{n,{\\bf d}$<\/jats:alt-text>\n\t <\/jats:inline-graphic> is \u0398(d<\/jats:italic>\/ln d<\/jats:italic>). This condition is satisfied by graphs with exponential tails as well those with power law tails.<\/jats:p>","DOI":"10.1017\/s0963548306008388","type":"journal-article","created":{"date-parts":[[2007,1,23]],"date-time":"2007-01-23T15:56:00Z","timestamp":1169567760000},"page":"733-746","source":"Crossref","is-referenced-by-count":7,"title":["On the Chromatic Number of Random Graphs with a Fixed Degree Sequence"],"prefix":"10.1017","volume":"16","author":[{"given":"ALAN","family":"FRIEZE","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MICHAEL","family":"KRIVELEVICH","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"CLIFF","family":"SMYTH","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2007,9,1]]},"reference":[{"key":"S0963548306008388_manual_ref-2","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2005.162.1335"},{"key":"S0963548306008388_manual_ref-6","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(80)80030-8"},{"key":"S0963548306008388_manual_ref-17","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1017\/S0963548398003526","article-title":"The size of the largest component of a random graph on a fixed degree sequence","volume":"7","author":"Molloy","year":"1998","journal-title":"Combin. Probab. Comput"},{"key":"S0963548306008388_manual_ref-18","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511721335.010"},{"key":"S0963548306008388_manual_ref-8","doi-asserted-by":"publisher","DOI":"10.1017\/S096354830400611X"},{"key":"S0963548306008388_manual_ref-4","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1999.1910"},{"key":"S0963548306008388_manual_ref-14","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90029-E"},{"key":"S0963548306008388_manual_ref-13","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(13)80042-X"},{"key":"S0963548306008388_manual_ref-3","doi-asserted-by":"publisher","DOI":"10.1080\/10586458.2001.10504428"},{"key":"S0963548306008388_manual_ref-1","first-page":"219","volume-title":"Proc. RANDOM 2004","author":"Achlioptas","year":"2004"},{"key":"S0963548306008388_manual_ref-16","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060204"},{"key":"S0963548306008388_manual_ref-10","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/0095-8956(92)90070-E","article-title":"On the independence and chromatic numbers of random regular graphs","volume":"54","author":"Frieze","year":"1992","journal-title":"J. Combin. Theory Ser. B"},{"key":"S0963548306008388_manual_ref-11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-7915-6_11"},{"key":"S0963548306008388_manual_ref-12","doi-asserted-by":"publisher","DOI":"10.1007\/BF01375472"},{"key":"S0963548306008388_manual_ref-15","doi-asserted-by":"publisher","DOI":"10.1007\/BF01275671"},{"key":"S0963548306008388_manual_ref-9","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548302005254"},{"key":"S0963548306008388_manual_ref-7","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122551"},{"key":"S0963548306008388_manual_ref-5","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(78)90059-6"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548306008388","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T07:52:16Z","timestamp":1750492336000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548306008388\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,9]]},"references-count":18,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2007,1]]}},"alternative-id":["S0963548306008388"],"URL":"https:\/\/doi.org\/10.1017\/s0963548306008388","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2007,9]]}}}