Plans for graph colouring.
More...
Go to the source code of this file.
Detailed Description
Plans for graph colouring.
 Todo:
 Connections to other modules

See ComputerAlgebra/Hypergraphs/Lisp/plans/Colouring.hpp.

In principle one can always generalise everything to hypergraphs, but in this module we consider the cases where graphs behave "special".

Yet, in OKlib/Combinatorics we have put also graph colouring to the hypergraph module there; perhaps we should change this.
 Todo:
 Greedy colouring

See "Greedy colouring" in ComputerAlgebra/Hypergraphs/Lisp/plans/Colouring.hpp for the hypergraph context.

See Hypergraphs/Colourings/plans/GreedyColouring.hpp for plans at C++ level, and see Combinatorics/Hypergraphs/Colourings/GreedyColouring.cpp for a C++ implementation.

DONE (yes, special algorithms are of interest) Should we also provide special functionality for graphs?

DONE (implemented greedy_colouring_og) Specifying input and output:

Input a graph and a vertex ordering, output the derived colouring, as a map.

More precisely, input is an ordered graph.

The output is a pair [n,M], where n is the number of colours used, while M is the colouring itself as a map.

Actually, it seems better to produce just the list of colours, using the given order of the vertices.

Colours are natural numbers from 1 to n.

To summarise: Input is an og G, output is a pair [n,C], where C is a list of numbers from 1 to n.

Calling it greedy_colouring_og(G).
Definition in file Colouring.hpp.