OKlibrary  0.2.1.6
Chapter03.hpp File Reference

Chapter "Colorings of graphs and Ramsey's theorem" from [A Course in Combinatorics]. More...

Go to the source code of this file.


Detailed Description

Chapter "Colorings of graphs and Ramsey's theorem" from [A Course in Combinatorics].

Brook's theorem

Greedy colouring

  • See "Greedy colouring" in ComputerAlgebra/Hypergraphs/Lisp/plans/Colouring.hpp.
  • Greedy graph colouring will always find a colouring using at most d + 1 many colours, where d is the maxima degree.
  • Likely it does not automatically yield a d-colouring if no component is an odd cycle or the graph does not contain a (d+1)-clique --- example?
  • Can this be repaired?
  • Or with other algorithms? Is it possible at all?

Ramsey's theorem

On the automorphism group of Ramsey hypergraphs

Finding Ramsey numbers via SAT

  • Some experimentation has been started in this area at Experimentation/Investigations/RamseyTheory/plans/RamseyProblems.hpp .

On the automorphism group of Ramsey clause-sets

Tournaments and transitive tournaments

  • See [Ramsey numbers for tournaments] by Y.Mannoussakis and Z.Tuza, and originally [A problem on tournaments] by P.Erdos and L.Moser, for work on treating tournaments and transitive subtournaments as a Ramsey-type problem, as well as other Ramsey-type problems of directed graphs.

The Lovasz local lemma

Definition in file Chapter03.hpp.