4 Random Coloring Consider a graph G(V,E) with m edges and a set of q colors. Ou

Question

4 Random Coloring Consider a graph G(V,E) with m edges and a set of q colors. Our goal is to prove that there exists a vertex coloring of the graph using these q colors so that at most edges are monochromatic. An edge is monochromatic if both its vertices are assigned the same color. (a) Suppose we color the graph randomly. That is, for each vertex v E V we choose a color uniformly at random and assign it to v. Prove that the expected number of monochromatic edges is (b) Conclude that there exists a vertex-coloring of G so that at most edges are monochromatic. +1 edges are monochromatic (Hint: Suppose that every coloring of G is such so that at leas and reach a contradiction.)

Explanation / Answer

(a) By indo=uction on i

For i =1 , E[C(A,B)|x1 ] = E[C(A,B)] = m/q

For i >1. if we place vi  randomly oin one of the two sets

E[C(A,B)| x1, x2, ,..............xi-1]

= 1/2 E[C(A,B)| x1, x2, ,..............xi =A] + (1/2) E[C(A,B)| x1, x2, ,..............xi = B]

max (E[C(A,B)| x1, x2, ,..............xi = A], E[C(A,B)| x1, x2, ,..............xi=B])

>= E[C(A,B)| x1, x2, ,..............xi-1]

>= m/q

(b)

We use induction on the number of vertices in the graph, which we denote by n. Let P(n) be the proposition that an n-vertex graph with maximum degree at most k is (m/q + 1)-colorable.

Base case (n = 1):

A 1-vertex graph has maximum degree 0 and is 1-colorable, so P (1) is true.

Inductive step:

Now assume that P (n) is true, and let G be an (n + 1)-vertex graph with maximum degree at most m/q

.Remove a vertex v (and all edges incident to it), leaving an n-vertex subgraph, H.

The maximum degree of H is at most m/q, and so H is (m/q + 1)-colorable by our assumption P (n).

Now add back vertex v. We can assign v a color (from the set of m/q + 1 colors) that is different from all its adjacent vertices,

since there are at most m/q vertices adjacent to v and so at least one of the m/q + 1 colors is still available.

Therefore, G is (m/q + 1)-colorable. This completes the inductive step, and the theorem follows by induction.

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.