I need to order the vertexes of a planar graph so that the greedy algorithm would colour the vertexes using 6 colours.Could you please give some sugestions or hints to what could I start with ?
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
Here's how it works:
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Order the vertices according to their degrees and you have the Welsh-Powell alogrithm that gives a 6-coloring if the max degree is 5 or less.