Graph Colouring Algorithms |
|
Since graph three-colouring is an NP-Complete problem we can expect
that there has been a lot of work on finding efficient algorithms.
We are only interested in exact algorithms that are guaranteed to
find a three-colouring, if it exists.
Trivialy we can accomplish this by a $3^n$ algorithm:
- For every vertex,
- Colour it with one of the three colours
- If it's legal - output the colouring
We can clearly improve that to $2^n$ as follows.
Assume the graph is connected and has at least two vertices. Then
- Choose an edge, colour its end-points "Red" and "Green".
- Repeatedly:
- If there's a vertex connected to all three colours:
- Repeatedly:
- For all vertices attached to two other colours:
- Colour them the only colour possible.
- Find an uncoloured vertex:
- Colour it each possible colour and recurse.
- (There is some freedom to choose here)
- (Probably choose a vertex with only a small number of options)
- (Also probably choose a vertex of large degree)
If we always choose a vertex that has at least one coloured neighbour
then this is bounded above by $2^n.$ Other algorithms improve the
$2^n$ bound, but are still exponential.
As mentioned, we can apply heuristics at each stage to the vertices we
choose. If the endpoints of our initial edge have large degree then they
have lots of implications for reducing the options elsewhere. Similarly,
when we choose the next possible vertex to colour we can choose a vertex
of large degree. This might help, but we can construct examples where it
doesn't. In random graphs, it probably will.
Links to this page /
Page history /
Last change to this page
Recent changes /
Edit this page (with sufficient authority)
All pages /
Search /
Change password /
Logout
