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 ?
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 ?