1
$\begingroup$

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}$:

enter image description here

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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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). $\endgroup$
    – Nathaniel
    Jun 21, 2021 at 11:48

1 Answer 1

Reset to default
2
$\begingroup$

Your algorithm is known as greedy coloring, and its properties are well-known.

When run on a complete bipartite graph, it always produces a 2-coloring (this is a nice exercise).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.