# 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).

## 1 Answer

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.

• 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). – R B Jan 10 '15 at 15:58