Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-22T19:15:05.009Z Has data issue: false hasContentIssue false

Sharp concentration of the equitable chromatic number of dense random graphs

Published online by Cambridge University Press:  26 November 2019

Annika Heckel*
Affiliation:
Mathematical Institute, University of Oxford, Andrew Wiles Building, Woodstock Road, Oxford OX2 6GG, UK Email: [email protected]

Abstract

An equitable colouring of a graph G 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 χ=(G) is the minimum number of colours required for this. We study the equitable chromatic number of the dense random graph ${\mathcal{G}(n,m)}$ where $m = \left\lfloor {p\left( \matrix{ n \cr 2 \cr} \right)} \right\rfloor $ and 0 < p < 0.86 is constant. It is a well-known question of Bollobás [3] whether for p = 1/2 there is a function f(n) → ∞ such that, for any sequence of intervals of length f(n), the normal chromatic number of ${\mathcal{G}(n,m)}$ lies outside the intervals with probability at least 1/2 if n is large enough. Bollobás proposes that this is likely to hold for f(n) = log n. We show that for the equitable chromatic number, the answer to the analogous question is negative. In fact, there is a subsequence ${({n_j})_j}_{ \in {\mathbb {N}}}$ of the integers where $\chi_=({\mathcal{G}(n_j,m_j)})$ 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/(2logbn) where b = 1/(1 − p).

Type
Paper
Copyright
© Cambridge University Press 2019

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

This research was partially funded by ERC grant 676632.

References

Alon, N. and Krivelevich, M. (1997) The concentration of the chromatic number of random graphs. Combinatorica 17 303313.CrossRefGoogle Scholar
Bollobás, B. (1988) The chromatic number of random graphs. Combinatorica 8 4955.CrossRefGoogle Scholar
Bollobás, B. (2004) How sharp is the concentration of the chromatic number? Combin. Probab. Comput. 13 115117.CrossRefGoogle Scholar
Erdős, P. and Rényi, A. (1960) On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. 5 1761.Google Scholar
Fountoulakis, N., Kang, R. and McDiarmid, C. (2010) The t-stability number of a random graph. Electron. J. Combin. 17 R59.Google Scholar
Hajnal, A. and Szemerédi, E. (1970) Proof of a conjecture of P. Erdős. Combin. Theory Appl. 2 601623.Google Scholar
Heckel, A. (2018) The chromatic number of dense random graphs. Random Struct. Alg. 53 140182.CrossRefGoogle Scholar
Krivelevich, M. and Patkós, B. (2009) Equitable coloring of random graphs. Random Struct. Alg. 35 8399.CrossRefGoogle Scholar
McDiarmid, C. (1989) On the method of bounded differences. In Surveys in Combinatorics, 1989 (Siemons, J., ed.), Vol. 141 of London Mathematical Society Lecture Note Series, Cambridge University Press, pp. 148188.CrossRefGoogle Scholar
McDiarmid, C. (1990) On the chromatic number of random graphs. Random Struct. Alg. 1 435442.CrossRefGoogle Scholar
Panagiotou, K. and Steger, A. (2009) A note on the chromatic number of a dense random graph. Discrete Math. 309 34203423.CrossRefGoogle Scholar
Rombach, P. and Scott, A. Equitable colourings of random graphs. Preprint.Google Scholar
Shamir, E. and Spencer, J. (1987) Sharp concentration of the chromatic number on random graphs Gn,p. Combinatorica 7 121129.CrossRefGoogle Scholar