Solution representation; or proving that our algorithms work

[Isinlor]

In the demonstration we will be asked why our chromatic numbers are correct.

See highlights on page 4 of the project description.

IMO the best way to prove that our upper bound and exact answers are correct is to actually give solution to the problem. (Any other ideas?)

How do we represent solution to the graph coloring problem?

Example graph:

VERTICES = 6
EDGES = 7
1 2
2 3
3 1
1 4
4 5
5 6
6 4

IMO a good solution representation would be:

COLORS = 3
1 6
2 4
3 5

First line indicate how many colors were used. Each following line represents one color. Each line lists vertices in ascending order, so that it is easy to check visually that there is no duplicates.

[Isinlor]

Another, possibly better representation (no duplicates per color is quite trivial property) would be:

VERTICES = 6
EDGES = 7
COLORS = 3
1 2 | 1 2
2 3 | 2 3
3 1 | 3 1
1 4 | 1 2
4 5 | 2 3
5 6 | 3 1
6 4 | 1 2

This allows to quickly check that for each edge no two vertices have the same color. E.g. Edge 6 4 (last line), assigns color 1 to vertex 6 and color 2 to vertex 4.