# Sharp concentration of the equitable chromatic number of dense random graphs

@article{Heckel2019SharpCO, title={Sharp concentration of the equitable chromatic number of dense random graphs}, author={A. Heckel}, journal={Combinatorics, Probability and Computing}, year={2019}, volume={29}, pages={213 - 233} }

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…

#### Topics from this paper

#### 3 Citations

Some extremal results on the chromatic-stability index

- Mathematics
- 2020

The $\chi$-stability index ${\rm es}_{\chi}(G)$ of a graph $G$ is the minimum number of its edges whose removal results in a graph with the chromatic number smaller than that of $G$. In this paper…

On the chromatic number in the stochastic block model

- Mathematics
- 2021

We prove a generalisation of Bollobás’ classical result on the asymptotics of the chromatic number of the binomial random graph to the stochastic block model. In addition, by allowing the number of…

On the chromatic number of graphons

- Mathematics
- 2021

We determine the asymptotic behaviour of the chromatic number of exchangeable random graphs defined by step-regulated graphons. Furthermore, we show that the upper bound holds for a general graphon.…

#### References

SHOWING 1-10 OF 15 REFERENCES

The chromatic number of dense random graphs

- Mathematics, Computer ScienceRandom Struct. Algorithms
- 2018

New upper and lower bounds for $\chi(G)$ are established, which narrow down the colouring rate $n/\chi( G)$ of $G \sim G(n,p)$ to an explicit interval of length $o(1)$ answering a question of Kang and McDiarmid.

How Sharp is the Concentration of the Chromatic Number?

- Mathematics, Computer ScienceCombinatorics, Probability and Computing
- 2004

The chromatic number of a random graph G_{n,m} is determined for the case $m=O(n)$, but when in the 1970s Erdős popularized the problem, he was asking for good estimates on the chromaticNumber of G_{{n,1/2}$ for $m \sim n^2/4$ (equivalently, the chromatics number of $G_{ {n, 1/2}}$.

Equitable coloring of random graphs

- Computer ScienceRandom Struct. Algorithms
- 2009

This paper investigates the asymptotic behavior of these coloring parameters in the probability space G(n, p) of random graphs and proves the equitable chromatic threshold of G is shown to be 0.99.

The chromatic number of random graphs

- Mathematics, Computer ScienceComb.
- 1988

It is shown that for a fixed probabilityp, 0<p<1, almost every random graphGn,p has chromatic number log (1/(1 - p) + o(1) + 1 + o (1)log n, where n is the number of random graphs.

The concentration of the chromatic number of random graphs

- Mathematics, Computer ScienceComb.
- 1997

We prove that for every constant δ>0 the chromatic number of the random graphG(n, p) withp=n−1/2−δ is asymptotically almost surely concentrated in two consecutive values. This implies that for any…

A note on the chromatic number of a dense random graph

- Computer Science, MathematicsDiscret. Math.
- 2009

This work improves the best known lower bound for the chromatic number of dense random graphs and shows in particular that the estimate @g(G"n","p)>[email protected](G" n","p), where @a denotes the independence number, is not tight.

The t-Stability Number of a Random Graph

- Mathematics, Computer ScienceElectron. J. Comb.
- 2010

The theme of this paper is the typical values that this parameter takes on a random graph on $n$ vertices and edge probability equal to $p$ for any fixed graph.

Sharp concentration of the chromatic number on random graphsGn, p

- Computer Science, MathematicsComb.
- 1987

The distribution of the chromatic number on random graphsGn, p is quite sharply concentrated. For fixedp it concentrates almost surely in √n ω(n) consecutive integers where ω(n) approaches infinity…

On the evolution of random graphs

- Mathematics
- 1984

(n) k edges have equal probabilities to be chosen as the next one . We shall 2 study the "evolution" of such a random graph if N is increased . In this investigation we endeavour to find what is the…

On the Chromatic Number of Random Graphs

- Mathematics, Computer ScienceRandom Struct. Algorithms
- 1990

An argument of Bollobas is refined to show that almost all random graphs with fixed edge-probability p have chromatic number equal to n/2 logbn − 2 logb logbn + O(1) where b = 1/(1 − p).