2
$\begingroup$

Let's consider a greedy algorithm for the coloration problem called the Dsatur algorithm, designed by Daniel Brélaz in 1979 at the EPFL, Switzerland.. This algorithm is based on an order of vertices which we can obtain from considering the saturation degree of each vertex $v$ from $G$. The saturation degree of a vertex $v$ , which we can write as $DSAT(v)$, is the number of color, the number of different colors used in $v$ neighborhood. The idea is to color first the vertices with a saturation degree high enough to avoid using too many colors.

Data : an undirected (*non-orienté*) connected graph $G=(V,E)$.
Output : all vertices of $G$ colored.

SORT the vertices by decreasing order of degrees.
COLOR a vertex of maximum degree with color 1.
While it exists vertices not colored do 
  CHOOSEa vertex $v$ with max DSAT
  COLOR $v$ with the smallest possible color
  UPDATE DSAT for all neighbors of v

How to show that DATSUR Algorithm always color optimally connected bipartite graphs ?

Bipartite graph example

My attempt

I think I have to prove it by the absurd :

  • As far as it is a conected graph it can't be colored by one color solely.
  • If there were three colors returned by the algorithm Dsatur, taht would mean that a vertex would return $Dsatur(v)= 2$ (it exists two neighbors with two different colors). Which is impossible. But why ?

That would mean that it gives three kind of different colors... But I don't know how to show why this is impossible... Can you help me ?

$\endgroup$
  • 1
    $\begingroup$ Try running the algorithm by hand on a few example graphs (small ones). Do you see any patterns? Try to write down some conjectures, then try to prove that those patterns will always hold on all possible graphs. Then, edit your question to show your attempts and progress and what specifically you're stuck with. $\endgroup$ – D.W. Mar 16 '17 at 15:21
3
$\begingroup$

You can prove an even stronger claim. Consider the following algorithm:

Let $v_1,\ldots,v_n$ be an ordering of the vertices such that for $i>1$, each $v_i$ is connected to at least one of $v_1,\ldots,v_{i-1}$.

Go over all vertices $v_1,\ldots,v_n$ in order, and color each one with the smallest available color.

This algorithm also uses (at most) two colors to color a connected bipartite graph. The property of the ordering that I highlight, which is satisfied by the ordering produced by the Dsatur algorithm, suffices to guarantee that the algorithm uses the minimal number of colors.

To prove that this algorithm works for a connected bipartite graph with bipartition $V_1 \cup V_2$, where $v_1 \in V_1$, prove by induction that if $v_i \in V_j$ then $v_i$ gets colored $j$.

$\endgroup$

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.