general.hpp File Reference

Plans for the module on hypergraph (and graph) colouring. More...

Go to the source code of this file.


namespace  OKlib::Combinatorics::Hypergraphs::Colourings

Components for hypergraph colouring.

namespace  OKlib

All components of the OKlibrary.

namespace  OKlib::Combinatorics

The part of the OKlibrary for general combinatorics.

namespace  OKlib::Combinatorics::Hypergraphs

Supermodule for dedicated hypergraph algorithms.

Detailed Description

Plans for the module on hypergraph (and graph) colouring.

Update namespace-usage.
Module structure
  • Given a (hyper)graph as input, translate the k-colouring problem into generalised or P-clause-sets.
Other implementations
  • What open-source graph colouring implementations are available?
  • Problem collections?
  • Are there competitions?
Active clause-sets
  • For interesting systematically generated classes of (hyper)graphs, create active clause-sets translating k-colouring problems.
Investigate the problem of determining the chromatic number:
  • For finding an optimal colouring for a graph G the following strategy seems natural:
    1. Find a reasonable upper bound chi(G) <= u by some quick heuristics (different forms of greedy colouring).
    2. Find a reasonable lower bound l <= chi(G) by some quick heuristics, among them finding cliques in G.
    3. 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:
    1. Find some lower bound l and some upper bound u.
    2. Close the gap with a (generalised) SAT solver.
  • And the same for strong hypergrap colouring.
Property B
  • Erdoes and Hajnal introduced the function m(k) associated with property B: The minimal number of hyperedges of non-2-colourable k-uniform hypergraphs.
  • Known are only m(0) = m(1) = 1, m(2) = 3, m(3) = 7 (see the latest OK-report (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 k-uniform non-2-colourable 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 "non-c-colourable", and to consider m(c, k) (with m(2, k) = m(k))).
Square hypergraphs
  • In [Robertson, Seymour, Thomas: Permanents, Pfaffian orientations, and even directed circuits] a poly-time algorithm for deciding whether a square hypergraph is minimal non-2-colourable is given; very interesting to investigate this algorithm.

Definition in file general.hpp.