Is there a name for this graph density measure? Let $G=(V,E)$ be an undirected graph.
We define the following procedure (randomized greedy coloring):

Fix some random ordering over the vertices (each permutation will be chosen w.p. $\frac{1}{|V|!}$).
Color the graph vertices according to the order such that each vertex gets colored by the minimal color not used already by its neighbors.

We define $\mathfrak C(G)$ to be the expected number of colors according to the procedure.

Is there a name for $\mathfrak C(G)$?


For example:

$\mathfrak C(K_n)=n$ (trivial, every vertex must get a new color regardless of the order).
$\mathfrak C(C_6)=2\frac{1}{5}$ (in a cycle on 6 nodes, if the second vertex that is colored is of distance 3 from the first colored vertex, the number of colors used will be 3).
I believe this is called the chromatic density of a finite graph. See page 8 of this reference. The notation is different, but I think it is the same concept.
I believe this is called the chromatic density of a finite graph. See page 8 of this reference. The notation is different, but I think it is the same concept.