In our continued testing of the program we generated some conjectures for upper bounds for the chromatic number. We told the program the upper bounds due to Brooks, Wilf, and Welsh-Powell – so the program can’t make a conjecture implied by any of these. These were tested for the few dozen graphs the program knows and then some number of small-ish graphs.

The program seems to have noticed there is a relations chip between the chromatic and clique numbers of a graph: the clique number shows up in a large number of the conjectures.

If you know a counterexample, please let us know. We still plan to add the Szekeres-Wilf bound. Dan Cranston suggests this will remove the first conjecture below.

1. chromatic_number(x) <= maximum_average_degree(x) + 1

2. chromatic_number(x) <= clique_number(x) + girth(x)

3. chromatic_number(x) <= clique_number(x) + domination_number(x)

4. chromatic_number(x) <= 2*clique_number(x) + 1

5. chromatic_number(x) <= clique_number(x) + 1/2*max_degree(x)