Plans for the module on hypergraph (and graph) colouring.
More...
Go to the source code of this file.
Detailed Description
Plans for the module on hypergraph (and graph) colouring.
 Todo:
 Update namespaceusage.
 Todo:
 Module structure
 Todo:
 Translations

Given a (hyper)graph as input, translate the kcolouring problem into generalised or Pclausesets.
 Todo:
 Other implementations

What opensource graph colouring implementations are available?

Problem collections?

Are there competitions?
 Todo:
 Active clausesets

For interesting systematically generated classes of (hyper)graphs, create active clausesets translating kcolouring problems.
 Todo:
 Investigate the problem of determining the chromatic number:

For finding an optimal colouring for a graph G the following strategy seems natural:

Find a reasonable upper bound chi(G) <= u by some quick heuristics (different forms of greedy colouring).

Find a reasonable lower bound l <= chi(G) by some quick heuristics, among them finding cliques in G.

Comprising the found cliques into hyperedges, a hypergraph G' is constructed (with chi_s(G') = chi(G), where chi_s is the strong colouring number), and then via a (generalised) SAT solver the interval l <= chi_s(G') <= u is narrowed to a point (perhaps here bisection is sensible?!); see Hypergraphs/Colourings/plans/StrongColouring.hpp for strong colourings of hypergraphs.

For finding an optimal colouring for a hypergraph G we should try the same strategy:

Find some lower bound l and some upper bound u.

Close the gap with a (generalised) SAT solver.

And the same for strong hypergrap colouring.
 Todo:
 Property B

Erdoes and Hajnal introduced the function m(k) associated with property B: The minimal number of hyperedges of non2colourable kuniform hypergraphs.

Known are only m(0) = m(1) = 1, m(2) = 3, m(3) = 7 (see the latest OKreport (XXX) on autarkies and hypergraph colouring), while 19 <= m(4) <= 23.

Given n, m, k, it should be possible to construct a nice SAT problem whose solutions are the kuniform non2colourable hypergraphs G with n vertices and m edges.

Then we can try to compute values for m(k).

This can also be generalised to higher chromatic numbers (in the literature there is the generalised property B(s)? it seems more natural to consider c >= 2 for "nonccolourable", and to consider m(c, k) (with m(2, k) = m(k))).
 Todo:
 Square hypergraphs

In [Robertson, Seymour, Thomas: Permanents, Pfaffian orientations, and even directed circuits] a polytime algorithm for deciding whether a square hypergraph is minimal non2colourable is given; very interesting to investigate this algorithm.
Definition in file general.hpp.