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$

1 Answer 1

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$
4
  • $\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$ Oct 13, 2021 at 10:12
  • $\begingroup$ Since this is likely a homework exercise, I'd rather not give complete details. $\endgroup$ Oct 13, 2021 at 10:24
  • $\begingroup$ @YuvalFilmus without knowing the algorithm which produced the chromatic number, how can you detect which edges to add? The chromatic number is known and it could be found in polynomial time is known. The unknown is the color assignment. I don't think its straight-forward. $\endgroup$ Apr 28, 2022 at 9:59
  • $\begingroup$ I beg to differ. $\endgroup$ Apr 28, 2022 at 10:01

Your Answer

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

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