Lower bound algorithm

[Isinlor]

Here we can keep track of work related to the lower bound algorithm.

This algorithm is optional.

Just as reminder: lower bound algorithm is an algorithm that produces some non-trivial lower bound on the chromatic number.

• [x] First we need to figure out how hard it is to implement such algorithm and whether it is worth doing it.
• [x] Please, provide links to resources, copy&paste relevant snippets here
• [x] Then we need to decide on algorithm that we will implement
• [ ] Implement the algorithm
• [ ] Prepare materials for the presentation

[Isinlor]

Exact algorithm from https://github.com/dke-group-23/DKE-Project/issues/3#issuecomment-427880224 allows to find lower bound.

Another idea based on Wikipedia:

If G contains a clique of size k, then at least k colors are needed to color that clique;

Also from Wikipedia

a clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent;

From math to human language it would be: If you can find some set of vertices, so that all vertices are connected to all other vertices in that graphs, then this set of vertices is a clique. I guess, as you would expect from the name ;) . It pretty mach follows that because everyone is connected to everyone we will need to color everyone in different color.

The problem is of course how to find clique.

[Seeeeeyo]

With the Bron-Kerbosch algorithm? Here is an explanation of it. http://www.dcs.gla.ac.uk/~pat/jchoco/clique/enumeration/papers/bronKerbosch.pdf

There are a lot of codes of this algorithm online

[Isinlor]

Seems like an useful video: Maximal Cliques(Bron–Kerbosch Algorithm).