Computational Algebra Seminar

There is no known polynomial time 4-colouring algorithm for planar graphs, except the algorithms derived from the proofs of the four-colour theorem (4CT) by Appel, Haken, Koch (1977) and Robertson, Sanders, Seymour, Thomas (1994).

Short of doing this, one way to colour planar graphs is to investigate the problem of finding k-flows in graphs:

There is an equivalence between k-colouring a planar graph and finding a k-flow in a graph.

Let G be a graph, E its edge set, and D an orientation of its edges.

For any vertex u of G, define E_u to be the set of edges in E with end-vertex u.

A k-flow for G is defined as a map f: E -> Z/kZ - { 0 } such that for all vertices u in G,

Σ_{e ∈ Eu} f(e) = 0.

If one could find a ``reasonable'' algorithm to construct a 4-flow (or a 3-flow) in a graph then one would have a ``reasonable'' algorithm to colour planar graphs. (Note that the decision problem is in general NP-complete.)

In my talk I will discuss these various issues and show how I used Magma's toolbox in this context.