Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Can you suggest a good rough graph colouring algorithm? What are the best such algorithms nowadays?

share|improve this question
    
What exactly do you mean by a graph coloring algorithm? –  Qiaochu Yuan Jan 12 '10 at 17:32
    
an algorithm that maps vertices to numbers from [1..k] such that no two adjacent vertices have the same number, and k is as small as possible. –  Suresh Venkat Jan 12 '10 at 17:45
    
I mean an algorithm of colouring of vertices of a graph in a proper way(vertices of the same colour aren't neighbours). Not precise (It is NP-complete problem) but a rough one. Maybe somebody knows what achievements in this field are made for today. –  Oleg Jan 12 '10 at 17:52
4  
"heuristic" does not mean "not precise"! I know it's often used that way but that's not what it means. –  Loop Space Jan 13 '10 at 10:25
add comment

7 Answers 7

An interesting approximation algorithm is the one by Wigderson. It shows how to color a 3-colorable graph with $O(\sqrt{n})$ colors. It's very simple:

If the maximum degree is less than $\sqrt{n}$, you're done (just color greedily). If there is a node of degree larger than $\sqrt{n}$, you know that it's neighborhood is two-colorable so two-color it and never use those colors again. Remove the vertex and its neighbors from the graph and continue.

There have been several follow-up works by Blum and the latest improvements use semidefinite programming.

See, for instance, http://www.cs.cmu.edu/~anupamg/adv-approx/lecture15.pdf

or,

http://www.cs.princeton.edu/~chlamtac/acc-stoc.ps

for the semidefinite programming approach.

share|improve this answer
add comment

For practical non-optimal purposes you might want to look at DSATUR, and this paper, which briefly describes some simple methods: http://www.math.tu-clausthal.de/Arbeitsgruppen/Diskrete-Optimierung/publications/2002/gca.pdf

share|improve this answer
add comment

You might find this survey article of use:

http://www.springerlink.com/content/r66452u84130n423/

share|improve this answer
    
Thank you. I don't have access to that article. –  Oleg Mar 13 '10 at 15:46
add comment

Oleg, there are also stochastic parallel approaches where you color all vertices simultaneously and randomly and apply the heuristic in parallel to all of the vertices. This mimics parallel distributed information processing in networks.

Can you give some details about the heuristic which you are working on?

share|improve this answer
add comment

If “heuristic graph coloring algorithms” means approximation algorithms for the chromatic number, it is very useful to read “A compendium of NP optimization problems” edited by Pierluigi Crescenzi and Viggo Kann (http://www.csc.kth.se/~viggo/wwwcompendium/node15.html), which provides references for the best-known approximability and inapproximability results as of 2000.

share|improve this answer
add comment

There are a number of heuristics that work fairly well. They all work by prescribing some kind of ordering on the vertices, and then coloring the vertices one by one, using the least unused color to color the next one.

  • First Fit does precisely the above, with an arbitrary initial ordering. It's fast, but needless to say performs rather poorly.
  • LDO orders the vertices in decreasing order of degree, the idea being that the large degree vertices can be colored more easily.
  • SDO (saturation degree ordering) is a variant on LDO where the vertices are ordered in decreasing order by "saturation degree", defined as the number of distinct colors in the vertex neighborhood.
  • IDO (incidence degree ordering) is a variant of SDO where the "degree" of a vertex is defined as the number of colored vertices in its neighborhood.

The latter two heuristics require the order to be rebuilt after each step, and so are more expensive, but there's empirical evidence suggesting that they do reasonably well, especially in parallel.

None of these algorithms come with any kind of formal guarantees, so be warned.

share|improve this answer
add comment

How to write an algorithm for coloring vertices of a graph in C#?

share|improve this answer
    
If you have a new question, ask it via the ask question button in the upper right corner. –  Julian Kuelshammer Jun 25 '13 at 7:32
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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