I'm reviewing for my midterm thats on friday, and I came across this question in my textbook that I can't figure out:
" Consider the following approach to vertex colouring. First, find a maximal independent set of vertices and colour these with colour 1; then find a maximal independent set of vertices in the remaining graph and colour those 2, and so on. Compare this algorithm with the greedy algorithm: which is better? "
It's from Graph Theory - Reinhard Diestel. I tried to find a solutions manual but can't find one. Any help will be good!
Thank you!!