Description
Az SG(n,k) Schrijver gráf csúcsait az [n]={1,2,...,n} halmaz azon k elemű részhalmazai alkotják, melyek nem tartalmaznak ciklikusan szomszédos elemeket, azaz olyanokat, amikben i és i+1 vagy n és 1 egyszerre előfordul.
Két ilyen csúcs akkor van összekötve, ha a megfelelő halmazok diszjunktak.
Ez a gráf feszített részgráfja a KG(n,k) Kneser gráfnak, ami az [n] halmaz összes k elemű részhalmazán van hasonlóan definiálva és amiről Lovász híres eredménye, hogy a kromatikus száma pontosan n-2k+2.
Schrijver Lovász topologikus módszerét használva észrevette, hogy még SG(n,k) kromatikus száma is ugyanennyi, de annak bármely csúcsát elhagyva ez már nem igaz, vagyis SG(n,k) csúcs-színkritikus.
Az előadásban további kritikussági tulajdonságokról lesz szó, például, hogy mely élei lehetnek színkritikusak SG(n,k)-nak, illetve, hogy SG(n,k) milyen feszített részgráfja (csúcs)kritikus a tört kromatikus számra nézve, amely paraméter szintén azonos értéket vesz fel a KG(n,k) és az SG(n,k) gráfokon.
Az eredmények egyik része Tardos Gáborral, másik része Gujgiczer Annával közös.