I'm trying to make an algorithm in C++ that will color the vertices of a planar graph with at most 6 colors. I was just looking for some pseudo code how to go about this to help me get started. Any help is appreciated. Thanks.
2
votes
@EdHeal I thought we stopped tagging homework? Sure sounds like it though.
- Prof. Falken
Yes it is. I know to use a doubly linked list and I think I should designate the first vertex of the non-vacuous j degree list of smallest j as vertex ui. Delete ui from the j degree list. For each vertex U’ that was adjacent to ui in G and remains in some degree list, say j’, delete - u’ from the j’ degree list and insert u’ in the j’ - 1 degree list. Have a for loop to assign each vertex the smallest color value (between 1-6) not occurring on the vertices adjacent to vi that have already been colored. How does that sound?
- OhioState22
Sounds like you have seen an extract of the same paper I linked below. The algorithm is fine... so what's the problem? (I recently coded this algorithm in Java, so can give pointers if you are more specific).
- Tim Gee
1 Answers
6
votes
See:
TWO LINEAR-TIME ALGORITHMS FOR FIVE-COLORING A PLANAR GRAPH by David Matula, Yossi Shiloach, Robert Tarjan
(Just Google this and you'll find a PDF of the paper).
So this is a paper on 5-coloring a planar graph in O(n) time, but it starts with a simple description on an algorithm for 6-coloring. Here's the important extract (apologies for the formatting, this is just a PDF scrape):
ALGORITHM 6 COLOR. Given an n vertex planar graph G in adjacency list form, this algorithm determines a 6-coloring of G. Step 1. [Establish degree lists.] For each j where 0- j - n - 1, form a doubly < < linked list of all vertices of G of degree j. - Step 2. [Label vertices smallest degree last.] For i = n, n - 1, n*- 1,. . . , 1 designate the first vertex of the non-vacuous j degree list of smallest j as vertex t/i. Delete vi from the j degree list. For each vertex U’ that was adjacent to tli in G and remains in some degree list, say f, delete u’ from the jr degree list and insert u’ in the j9 - 1 degree list. Step 3. [Color vertices.] For i = 1,2,. . . , n, assign vertex t)i the smallest color value (which must be some integer between one and six) not occuring on the vertices adjacent to t)i that have already been colored.
