Parameter-Abhängigkeiten

wir kennen $\alpha$,$\delta$,$\Delta$,$\chi$, girth,$\omega$. untersuche

• Abhängigkeiten

  Beispiel: $\forall$G : $\omega$(G)$\le$$\Delta$(G) + 1

• und Unabhängikeiten

  Beispiel: $\forall$n : $\exists$G : $\Delta$(G)$\ge$n $\wedge$ $\omega$(G) = 2

Aufgabe: Finde solche Beispiele, z. B. mit $\chi$, girth.

Aufgabe: mit n = | V(G)|, zeige 2$\sqrt{n}$$\le$$\chi$(G) + $\chi$($\overline{G}$)$\le$n + 1.

Finde Graphen G, die beweisen, daß die Schranken nicht verbessert werden können. (D. h. für jedes n zwei Beispiele.)