# How many colors will be used in the following bipartite graph

I decided to create an algorithm to find the colors that is used to color a bipartite graph, the algorithm proceeds as follows:

• Rename the vertices in a some order $$v_1,v_2,\ldots,v_n$$.

• Do a single pass through all vertices of the graph, starting from $$v_1$$.

• To each $$v_i$$ assign the smallest available color not used among its already colored neighbors.

Now I have consider the following graph, $$K_{4,4}$$:

The question, I have is that, I have ordered the vertices in the graph. How many colors will be used here? The algorithm is giving me 7, I don't know why?

One very important question that I have is, will the change in orderings, would get the maximum and minimum colors? I think yes, but I am not getting it.

• I think there is a problem in your test, because your algorithm should find two colors used in your graph, not seven. And actually, since your graph is complete bipartite, your algorithm should always find two colors, no matter the ordering (I think this can be shown by induction). Jun 21 at 11:48