Colouring.hpp File Reference

Plans for graph colouring. More...

Go to the source code of this file.

Detailed Description

Plans for graph colouring.

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.
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:
    1. Input a graph and a vertex ordering, output the derived colouring, as a map.
    2. More precisely, input is an ordered graph.
    3. The output is a pair [n,M], where n is the number of colours used, while M is the colouring itself as a map.
    4. Actually, it seems better to produce just the list of colours, using the given order of the vertices.
    5. Colours are natural numbers from 1 to n.
    6. To summarise: Input is an og G, output is a pair [n,C], where C is a list of numbers from 1 to n.
    7. Calling it greedy_colouring_og(G).

Definition in file Colouring.hpp.