Graphenfärbung: Würfel sollte sich etwas darum bemühen, daß die chromatische Zahl nicht kleiner ist

eventuell geht das nicht (zu wenige Kanten), aber vielleicht doch.

trivial: wir bauen eine Clique der Größe chi(G)-1 ein.

besser: es gibt keine solche Clique.

ist aber beides teuer (Färbung bestimmen, Clique finden)

für kleine Parameter sollte es gehen