1
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ This question has been asked before... $\endgroup$
    – Yuval Filmus
    Jun 9, 2015 at 20:17

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$

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