# 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:

1. $$\mathfrak C(K_n)=n$$ (trivial, every vertex must get a new color regardless of the order).
2. $$\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).

• The two seems related, but can you please explain why they are the same? Especially, since the chromatic density is in $[0,1]$, how do you get to $\mathfrak C$ from it? (multiplying by $n^n$ doesn't seem right).