Matematikai Lapok 1967/1-4. [antikvár]

KROMATIKUS GRÁFOKRÓL ERDŐS PÁL ÉS HAJNAL ANDRÁS Egy G gráfot akkor nevezünk ?-kromatikusnak (a:(G) = /c), ha szögpontjait be lehet osztani k osztályba úgy, hogy két egy osztályba eső pont sincsen összekötve, s k — 1 ilyen osztályba a szögpontokat nem lehet beosztani. Ha m végtelen számosság, akkor G-t akkor nevezzük m-kromatikusnak, ha szögpontjait be lehet osztani m olyan osztályba, hogy két egy osztályba eső pont sincs összekötve, de ha non, akkor n ilyen osztályba a szögpontokat már nem lehet beosztani. Ha G tartalmaz egy k pontból álló teljes gráfot, akkor kromatikus száma nyilván legalább k. Tutte, Zykov és Ungár [10] egymástól függetlenül bebizonyították, hogy minden fc-ra van oly ?-kromatikus gráf, mely nem tartalmaz háromszöget. Erdős [3] valószínűségszámítási módszerekkel bebizonyította, hogy minden k és /-re van ?-kromatikus gráf, melynek mindén köre legalább / élű. Lovásznak sikerült ezt nemrég egy direkt konstrukcióval, kimutatnia. Erdős és Rádo [4] bebizonyították, hogy ha tetszés szerinti végtelen számosság, akkor mindig van oly G gráf, melyben a szögpontok számossága m, a gráf nem tartalmaz háromszöget, s /n-kromatikus. A szerzők [5] nemrég bebizonyították, hogy e tétel a következőképpen élesíthető: Legyen mg és / tetszőleges adott szám, ?kor van m szögpontú gráf, melynek legkisebb páratlan köre legalább 2/+1 élt tartalmaz, s mely m-kromatikus. Igen érdekes jelenség ezzel szemben a következő [5]: Legyen G tetszés szerinti számosságú gráf, mely nem tartalmaz négyszöget (azaz 4 élű kört), akkor %(G)SK0- ([3]-ból viszont rögtön következik, hogy minden /-re van oly G, melynek minden köre legalább l élű, s melyre h(G) = K 0-) Ezen eredmények mutatják, hogy egy gráf kromatikus száma lehet 80> bár a gráf nem tartalmaz kis kört. E cikkben egy más természetű idevágó kérdéssel fogunk foglalkozni. Előbb néhány egyszerű fogalmat kell bevezetnünk. Legyenek , xm a G gráf tetszés szerinti szögpontjai. G(xl5 , xm) legyen az xly , x„, szögpontok által feszített részgráf (azaz G(x1, , xj-ben xt és xJt akkor és csakis akkor vannak éllel összekötve, ha G-ben is össze vannak kötve). G szögpontjainak egy részhalmazát akkor nevezzük függetlennek, ha az általuk feszített részgráfnak nincsen éle (azaz, ha semmilyen szögpont sincs" éllel összekötve). /(G) jelentse á G legnagyobb független halmazának számosságát, feltéve, hogy ez végesIBazaz más szóval: G-nek van/(G) szögpontból álló független részhalmaza, de már/(G) +1 szögpontú független részhalmaza nincsen. Egy G gráfról akkor mondjuk, hogy megvan a Tc tulajdonsága, ha minden véges m-re és minden xt\ , xm szögpontra f(G(x1, , xm)) ^cm. Első pillanatban úgy gondolhatnánk, hogy ha G-nek megvan a Tc tulajdonsága, akkor n(G) sem lehet nagy. re ez majdnem nyilvánvaló. Ha ugyanis G-nek megvan a Ti tulajdonsága, akkor G-nek nem lehet páratlan köre, ti. ha x1} , x2l+1 G-nek egy páratlan köre lenne, akkor nyilván f(G,(x 1