3
$\begingroup$

Suppose we are given a graph $G$ of order $n$ and a black box that can efficiently (polynomial time) compute the chromatic number $\chi(G)$. I am curious to hear how would one go about in order to construct a proper coloring of $G$, more precisely

Find an efficient algorithm (polynomial time) to construct a proper coloring of $G$ provided that you can efficiently compute the chromatic number.

Does anybody see a simple algorithm for this purpose?

$\endgroup$
3
$\begingroup$

As long as possible, add edges to $G$ which do not increase the chromatic number. You should get a complete multipartite graph which corresponds to an optimal coloring.

$\endgroup$
2
  • $\begingroup$ I'm sorry, but could you elaborate a bit? I don't see how adding new edges (and turning this graph into a multigraph) assists in finding the coloring. $\endgroup$
    – Marik S.
    Oct 13 '21 at 10:12
  • $\begingroup$ Since this is likely a homework exercise, I'd rather not give complete details. $\endgroup$ Oct 13 '21 at 10:24

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.