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