Andi on-line

Ich war so stolz. Letzte Woche habe ich ein erstes Ergebnis produziert, das es tatsächlich in meine Diss schaffen hätte können. Vorerst nur eine Vermutung, aber ich war sicher, dass sich ein Beweis finden lassen würde. Es geht um folgendes:

Wenn ich für einen Graph bestimmte Subgraphen H verbiete, kann dieser Graph dann noch hohen Minimalgrad (delta(G) = cn) und gleichzeitig große chromatische Zahl haben?

Mit anderen Worten: erzwingt die Tatsache, dass es viele Kanten gibt, für diese Graphen eine gute Färbbarkeit? Interessant dabei ist, dass je nach Wahl von H die Antwort auf diese Frage unterschiedlich ausfällt. So ist z.B. bekannt, dass für H = Dreieck gilt: die chromatische Zahl ist unbeschränkt, falls delta(G) < (1/3 – epsilon) n ist und beschränkt, falls delta(G) < (1/3 + epsilon)n. Andererseits wird für H = Fünfkreis vermutet, dass die chromatische Zahl für jeden Minimalgrad der Form cn beschränkt ist.
Meine Lemma hätte etwas über die Situation für Graphen ohne Cliquen auf k Knoten ausgesagt. Dazu gibt es eine gute und eine schlechte Nachricht: die gute ist, dass das Lemma tatsächlich genau so stimmt, wie ich vermutet hatte. Die schlechte ist, dass das schon 1974 von drei Ungarn bewiesen wurde. Wieder nix für die Diss. Aber es bleibt ja noch das Problem für Fünfkreise…