Vera Weil
Universität zu Köln

Graphen in denen die Differenz zwischen dem Maximalgrad und der Cliquenzahl durch eine Konstante beschränkt ist

Für jede feste Zahl k aus den natürlichen Zahlen mit Null betrachten wir die Graphen, für die vererbend gilt, dass der Maximalgrad kleiner gleich der Cliquenzahl minus eins plus k ist. Das heißt, für jeden induzierten Subgraphen ist die Differenz zwischen dem Maximalgrad des Subgraphen und der Cliquenzahl des Subgraphen durch die Konstante k-1 beschränkt. Für jedes k können wir eine Charakterisierung durch eine endliche Menge minimal verbotener Subgraphen angeben. Die Resultate können beispielsweise auf die chromatische Zahl angewendet werden, so haben wir uns mit folgender Vermutung von B. Reed beschäftigt: Vermutung: "Die chromatische Zahl ist für jeden Graphen beschränkt durch folgenden Wert, aufgerundet: (Maximalgrad plus Cliquenzahl plus eins) durch 2." Für k kleiner oder gleich 3 liefert unsere Charakterisierung eine vererbende Graphenklasse, für welche die Reed'sche Vermutung gilt.