1
$\begingroup$

This question already has an answer here:

For the graph colourability problem, we are given a graph and our goal is to find a colouring of the graph with the fewest possible number of colours so that no two adjacent vertices have the same colour. This problem is known to be NP complete.

Suppose that we have an algorithm $A$ that runs in polynomial time and tells us whether our graph can be coloured by using $\leq k$ colours. We can query this algorithm as many times as we want.

Would this imply that the graph colourability problem also be in $P$?

My approach would be to begin querying for $k=1$, and then keep incrementing $k$ until we get a positive response from $A$, which is going to be the answer to our problem.

However, if we know how many colours we can use to colour our graph, how do we then actually colour each node? Is there a known algorithm for this?

$\endgroup$

marked as duplicate by D.W., Luke Mathieson, Juho, David Richerby, Rick Decker Jun 10 '15 at 12:48

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ This question has been asked before... $\endgroup$ – Yuval Filmus Jun 9 '15 at 20:17
1
$\begingroup$

Hint: If there is a valid coloring in which vertices $x,y$ get the same color then the graph resulting from merging $x,y$ into a single vertex has the same chromatic number. Otherwise, you can add an edge between them (if it doesn't already exist). Either way, the graph "simplifies" (either the number of vertices decreases, or the graph gets closer to a clique).

$\endgroup$

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