1
$\begingroup$

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).
|cite|improve this question
$\endgroup$
-1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – R B Jan 10 '15 at 15:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.