# How may an algorithm always color optimally connected bipartite graphs?

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 ?

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

• 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.
– D.W.
Mar 16, 2017 at 15:21

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.
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$$.