A következő (december 9 (péntek))

Legyen ${\cal S}$ szakaszok halmaza a $d$ dimenziós térben. Ezek {\em metszésgráfja} $M({\cal S})$ egy olyan gráf, amelynek csúcsai a szakaszoknak felelnek meg, két csúcs pontosan akkor van összekötve, ha a megfelelő szakaszok metszik egymást. Ennek komplementere $D({\cal S})$, ${\cal S}$ {\em diszjunktság gráfja}.

Közismert, hogy egy egyenesen levő szakaszok metszésgráfja és diszjunktság gráfja perfekt, így ezekre a kromatikus szám, $\chi$, egyenlő a klikkszámmal, $\omega$-val. Ugyanakkor a síkon levő szakaszok esetén már elképzelhető, hogy a metszésgráf klikkszáma $\omega(M)=2$, miközben a kromatikus szám $\chi(M)$ tetszőlegesen nagy.

A diszjunktság gráfnál ez nem lehetséges, síkbeli szakaszok diszjunktság gráfjára $\chi(D)\le \omega(D)^4$. Ezt az eredményt általánosítva belátjuk, hogy ha a szakaszok a $d$ dimenziós térben vannak ($d\ge 3$), akkor $\chi(D)\le \omega(D)^4+\omega(D)^3$. Ennél erősebb korlátokat bizonyítunk, ha szakaszok helyett egyeneseket tekintünk a $d$ dimenziós térben. Viszont szakaszok helyett görbékre nem általánosíthatók az eredmények.

Közös munka Pach Jánossal és Tardos Gáborral.

Minden erdeklodot szeretettel varunk, Peter