{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:30:42Z","timestamp":1759638642228},"reference-count":13,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2019,11,26]],"date-time":"2019-11-26T00:00:00Z","timestamp":1574726400000},"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":[[2020,3]]},"abstract":"Abstract<\/jats:title>An equitable colouring<\/jats:italic> of a graph G<\/jats:italic> is a vertex colouring where no two adjacent vertices are coloured the same and, additionally, the colour class sizes differ by at most 1. The equitable chromatic number \u03c7<\/jats:italic>=(G<\/jats:italic>) is the minimum number of colours required for this. We study the equitable chromatic number of the dense random graph ${\\mathcal{G}(n,m)}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> where $m = \\left\\lfloor {p\\left( \\matrix{\n n \\cr \n 2 \\cr} \\right)} \\right\\rfloor $<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and 0 < p<\/jats:italic> < 0.86 is constant. It is a well-known question of Bollob\u00e1s [3] whether for p<\/jats:italic> = 1\/2 there is a function f<\/jats:italic>(n<\/jats:italic>) \u2192 \u221e such that, for any sequence of intervals of length f<\/jats:italic>(n<\/jats:italic>), the normal chromatic number of ${\\mathcal{G}(n,m)}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> lies outside the intervals with probability at least 1\/2 if n<\/jats:italic> is large enough. Bollob\u00e1s proposes that this is likely to hold for f<\/jats:italic>(n<\/jats:italic>) = log n<\/jats:italic>. We show that for the equitable<\/jats:italic> chromatic number, the answer to the analogous question is negative. In fact, there is a subsequence ${({n_j})_j}_{ \\in {\\mathbb {N}}}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> of the integers where $\\chi_=({\\mathcal{G}(n_j,m_j)})$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is concentrated on exactly one explicitly known value. This constitutes surprisingly narrow concentration since in this range the equitable chromatic number, like the normal chromatic number, is rather large in absolute value, namely asymptotically equal to n<\/jats:italic>\/(2logb<\/jats:italic><\/jats:sub>n<\/jats:italic>) where b<\/jats:italic> = 1\/(1 \u2212 p<\/jats:italic>).<\/jats:p>","DOI":"10.1017\/s0963548319000397","type":"journal-article","created":{"date-parts":[[2019,11,26]],"date-time":"2019-11-26T10:38:48Z","timestamp":1574764728000},"page":"213-233","source":"Crossref","is-referenced-by-count":3,"title":["Sharp concentration of the equitable chromatic number of dense random graphs"],"prefix":"10.1017","volume":"29","author":[{"given":"Annika","family":"Heckel","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2019,11,26]]},"reference":[{"key":"S0963548319000397_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579208"},{"key":"S0963548319000397_ref12","unstructured":"[12] Rombach, P. and Scott, A. Equitable colourings of random graphs. Preprint."},{"key":"S0963548319000397_ref8","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20264"},{"key":"S0963548319000397_ref7","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20757"},{"key":"S0963548319000397_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2008.09.019"},{"key":"S0963548319000397_ref6","first-page":"601","article-title":"Proof of a conjecture of P. Erd\u0151s","volume":"2","author":"Hajnal","year":"1970","journal-title":"Combin. Theory Appl."},{"key":"S0963548319000397_ref4","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Erd\u0151s","year":"1960","journal-title":"Publ. Math. Inst. Hungar. Acad. Sci."},{"key":"S0963548319000397_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122551"},{"key":"S0963548319000397_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215914"},{"key":"S0963548319000397_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107359949.008"},{"key":"S0963548319000397_ref5","doi-asserted-by":"crossref","first-page":"R59","DOI":"10.37236\/331","article-title":"The t-stability number of a random graph","volume":"17","author":"Fountoulakis","year":"2010","journal-title":"Electron. J. Combin."},{"key":"S0963548319000397_ref10","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010404"},{"key":"S0963548319000397_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548303006060"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548319000397","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,25]],"date-time":"2020-03-25T08:15:01Z","timestamp":1585124101000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548319000397\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,26]]},"references-count":13,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,3]]}},"alternative-id":["S0963548319000397"],"URL":"https:\/\/doi.org\/10.1017\/s0963548319000397","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,26]]}}}