Problem 2. (10 points) Let G= ( V,E ) be a graph for which each vertex is colore
ID: 3718053 • Letter: P
Question
Problem 2. (10 points) Let G= ( V,E ) be a graph for which each vertex is colored either black or white (but not both). We say that vertex v is integrated if at least half of its neighbors (those connected by one edge to v) have a different color than . Furthermore, we say that a coloring of a graph is integrated if every vertex in the graph is integrated.
(a) Show that every graph in which every cycle is of even length has an integrated coloring. Consider the following algorithm: pick an uncolored vertex, color it white, color each of its neighbors black and repeat. Why will this procedure terminate in an integrated coloring?
(b) Prove that every graph has an integrated coloring. Consider the following algorithm: First, color every vertex white. Next, if there is a vertex that is not integrated, flip its color.
When this algorithm terminates, it will yield an integrated coloring. Prove that the process always terminates. (Hint: focus on the number of mixed edges – those whose end-points are of different colors.) What logical principle did you use to prove termination?
Explanation / Answer
The idea of the algorithm is as follows. We start with an arbitrary vertex s, color it Red, and run BFS from there in order to color all vertices in the same connected component with s. It is necessary that all neighbors of s are colored Blue, and all neighbors of these neighbors are colored Red, etc. If at some point we detect a vertex that is colored by two different colors, then the graph is not 2-colorable. After doing BFS at s, if there are uncolored vertices in G we choose one of them and repeat the same process.
The algorithm:
We will use the adjacency list representation for the graph. In this representation, each vertex v is associated with a linked list Adj[v] that contains all the neighbors of v. We will use an array Color, where Color[v] is the color of vertex v. Initially Color[v] = null for all vertices v.
1. % main for-loop: do BFS while there are unvisited vertices
2. for v in V do
3. if Color[v] = null do % vertex v has not been visited
4. % now do BFS at v
5. initialize an empty queue Q
6. Color[v] ? Red
7. Enqueue(Q, v)
8. while Q is not empty do
9. u ? Dequeue(Q) % take an element from the queue
10. for each w in Adj[u] do
11. if Color[w] = null do % w has not been visited
12. if Color[u] = Red
13. Color[w] ? Blue
14. else
15. Color[w] ? Red
16. end if
17. Enqueue(Q, w)
18. else if Color[w] = Color[u]
19. output NO
20. end if
21. end for
22. end while
23. end if
24. end for
25. output YES
Running time: The total time for all “for” loops (line 10) that are executed is O(|E|), because each loop corresponds to an edge of G. Thus the total running time is O(|V | + |E|).
Proof of correctness: There are two parts.
Part I. First we show that if the algorithm rejects (output NO) then the graph is not 2-colorable. Because every two BFS trees are not connected, the coloring for each tree is independent of each other. Suppose that the algorithm outputs NO during the BFS tree T that starts at a vertex v, we will show that this tree is not 2-colorable, and hence the whole graph is also not 2-colorable. Suppose for a contradiction that T is 2-colorable, then any 2-coloring of T is completely determined by the color of v, and we can assume without loss of generality that v has color Red. We prove the following Claim by induction on the distance from a vertex u to v.
Claim: Let u be a vertex in T. Any color that u gets from the program is the color that u must get in a 2-coloring of T where v is colored Red.
Proof of Claim For the base case, the distance from u to v is 0, i.e., u is v itself. The Claim holds in this case because v is colored Red.For the induction step, suppose that the distance from u to v is d+ 1 for some d ? 0. Therefore there is a neighbor u ? of u such that the distance from u ? to v is d. By the induction hypothesis the color assigned to u ? by the program is the color u ? must get in a 2-coloring of T where v is Red. Given the color of u ? , u has only once choice and it’s clear that this is the choice chosen by the program. This completes the induction step, and hence the proof of the Claim. We reach a contradiction because some vertex u in T is colored both Red and Blue by the program.
Part II. Now we show that if the program outputs YES, then indeed the graph is 2-colorable. This is so because the program actually provides a 2-coloring of the graph. This is because the BFS algorithm colors every vertex of the graph, and for any edge (u, v) the two endpoints must have different colors, for otherwise the program would outputs NO.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.