Solve graph coloring prob with a greedy algorithm in exponential time

Question

I'm currently teaching myself about algorithms and about different problems that are interesting in CS. For an example if I wanted to solve the graph coloring problem with a greedy algorithm (e.g. choose what's best at the moment) and ensure that I have the correct solution, then I'd basically have to go through the graph more than one time, if I'm correct? Because choosing what's best at the moment is generally not optimal and might give wrong results.

To be more specific, I'd actually want to answer the decision problem: Is the graph G colorable with N colors? with a greedy algorithm, and the answer certainly needs to be correct.

So are there any example algorithms in pseudo code out there - or can I get a clue how I can make sure that I give the correct answer with this greedy algorithm?

Thanks in advance! I appreciate any reply

Answer 1

From my understanding, for problems like this, greedy might not always give a correct solution since a graph may contain cycles and you might not be aware of certain edges to nodes until you reduce your space to a few nodes and you're left with incompatible colors. A basic solution to this would be a backtracking algorithm. It might be possible to use greedy in this case if you can reduce this problem to another NP problem that has a greedy solution but to the extent of my knowledge, I am not aware of one.