50 éves lett a perfekt gráf tétel

1. Bevezető

Lovász László 2021-ben megkapott Abel-díja jó alkalmat szolgáltat arra, hogy áttekintést adjunk híresebb eredményeiről. Ebben a cikkben az egyik első világraszóló eredményéről, a perfekt gráf sejtésről lesz szó.

Lovász László 50 évvel ezelőtt, 1971-ben bizonyította és 1972-ben megjelent cikkében publikálta bizonyítását a perfekt gráf sejtésre [15], amely így azóta Lovász tétel vagy perfekt gráf tétel. Továbbá egy szintén 1972-ben megjelent másik dolgozatában [16] megadta a perfekt gráfoknak egy olyan karakterizációját, amelyből szintén következett a perfekt gráf sejtés bizonyítása. Az eredmény és a bizonyítások egyből a kombinatorikai alapműveltség részévé lettek, azóta is lényegében minden gráfelméleti alapozó kurzus kimaradhatatlan részei. Ha hatásukat számokkal szeretnénk jellemezni, akkor talán a két cikk idézettsége a megfelelő mutatószám: [15]-re 928, míg [16]-ra 477 idézőt számol a Google Scholar így 2021. május végén.

A továbbiakban egy rövid, bevezető jellegű írást közlünk a tételről, ami remélhetőleg komolyabb kombinatorikai tudás nélkül is követhető lesz, legalább a nagy kép tekintetében. Először a tétel állításával ismerkedünk meg, majd arról mondunk pár szót, és hogy mi motiválta a perfekt gráf fogalmát és magát a sejtést (hogyan kapcsolódik a téma a korábbi eredményekhez), végül a bizonyításról és néhány azóta született eredményről lesz szó.

Ahhoz, hogy magát a perfekt gráf tételt ki tudjuk mondani, előbb pár fogalmat be kell vezetnünk. Egy (egyszerű, irányítatlan) $G$ gráf egy $V(G)$ csúcshalmazból és egy $E(G)$ élhalmazból áll, ahol az élek csúcspároknak felelnek meg, tehát az élhalmaz az összes csúcspárok halmazának egy részhalmaza. Egy $G$ gráf $H$ részgráfján olyan $H$ gráfot értünk, melyre igaz, hogy $V(H)$ részhalmaza $V(G)$ -nek és $E(H)$ részhalmaza $E(G)$ -nek. $G$ egy $F$ feszített részgráfján $G$ -nek olyan $F$ részgráfját értjük, amelyre igaz, hogy $E(F)$ pontosan a $V(F)$ csúcsai közt menő $G$ -beli élekből áll (tehát az összes olyan él halmaza, amelyet $V(F)$ -beli pontok $G$ -ben „kifeszítenek”)¹.

1. ábra. Egy 4-csúcsú gráf részgráfja és feszített részgráfja

Egy $G$ gráf komplementerén azt a $\overline{G}$ gráfot értjük, amelyre igaz, hogy a csúcshalmaza ugyanúgy $V(G)$ , mint $G$ -nek, de $V(G)$ csúcspárjaiból pontosan azokat tesszük bele az élhalmazba, amiket $G$ ‑be nem (azaz, ha valami él volt $G$ -ben, most nem lesz az és ha nem volt az, most az lesz).

2. ábra. Egy gráf és komplementere

A $K_n$ -nel jelölt $n$ csúcsú teljes gráfon azt a gráfot értjük, amelyben bármely két különböző csúcs élt alkot. Egy adott $G$ gráf esetén azt a legnagyobb $k$ számot, amelyre $G$ -nek van $K_k$ (-val izomorf²) részgráfja, $G$ klikkszámának mondjuk és $\omega(G)$ -vel jelöljük. Tehát pl. az 1. ábra (bal oldalán) látható gráfot felismerhetjük: $K_4$ , aminek a klikkszáma, $\omega(K_4)=4$ .

A $G$ gráfban egy független csúcshalmaz³ egy olyan $X$ részhalmaza $V(G)$ -nek, amelyre igaz, hogy $X$ -beli csúcsok közt nincsenek élek $G$ -ben. A legnagyobb olyan $k$ számot, amelyre igaz, hogy van $G$ -ben $k$ csúcsot tartalmazó független halmaz, $G$ függetlenségi számának nevezzük és $\alpha(G)$ -vel jelöljük. Ha már bevezettünk pár fogalmat, akkor most pihenésképp kicsit gyakoroljunk, próbáljuk meg őket összekapcsolni és gondoljuk végig, hogy $\alpha(G)$ a legnagyobb olyan $k$ szám, amelyre $K_k$ részgráfja $\overline{G}$ -nek, tehát $\alpha(G)=\omega(\overline{G})$ .

Az utolsó fogalom, amire a perfekt gráf tétel kimondása előtt szükségünk van, a kromatikus szám. Egy $k$ pozitív egész számra a $G$ gráf csúcsainak egy jó -színezésén azt értjük, hogy kiszínezzük a csúcsait legfeljebb $k$ színnel, méghozzá úgy, hogy éllel összekötött csúcsok különböző színeket kapjanak. (Az alábbi ábrán egy gráf 3 színnel való jó színezését látjuk.) Azt a legkisebb $k$ pozitív egész számot, amire a $G$ gráfnak van jó $k$ -színezése, a gráf kromatikus számának nevezzük és $\chi(G)$ -vel jelöljük.

Egy színezésnél az azonos színt kapott csúcsok halmazát színosztály(ok)nak mondjuk. Hogy a kromatikus számot is összekössük az előző fogalmakkal, vegyük észre, hogy minden színosztály független csúcshalmazt alkot (a színezési szabály szerint nem lehet él két azonos színű csúcs közt), tehát egy gráf jó $k$ -színezése ugyanazt jelenti, mint csúcsainak $k$ független csúcshalmazba való osztása.

3. ábra. Egy 4-pontú gráf jó színezése 3 színnel

Ugyan a fogalmak bevezetésén túl vagyunk, de a tétel kimondása előtt még próbáljuk meg összehasonlítani a két mennyiséget: $\omega(G)$ -t és $\chi(G)$ -t. Amire kis gondolkodással rájöhetünk, hogy $\chi(G) \ge \omega(G)$ fennáll, hiszen egy $\omega(G)$ csúcsszámú teljes részgráfban bármely két (különböző) csúcsot különböző színekkel kell színezni, ami így ad egy alsó becslést $\chi(G)$ -re. ⁴

Ennyi előkészület után bevezetjük a perfekt gráf fogalmát, amelyet Claude Berge⁵ egy 1960 áprilisában Halle-Wittenbergben megtartott gráfelméleti konferencia konferenciakötetében [1] definiált először. Egy $G$ gráfot perfektnek mondunk, ha minden feszített $G'$ részgráfjára (így például az egész $G$ gráfra is) igaz, hogy $\omega(G') = \chi(G')$ . Tehát kissé pongyolán úgy fogalmazhatunk, hogy $G$ bármely feszített részgráfjának a kromatikus számát csak a legnagyobb klikk mérete befolyásolja, a színezésnél nincsenek további plusz „akadályok”. A fogalom további motivációiról kicsit később lesz szó.

Az olvasó könnyen beláthatja, hogy a teljes gráfok vagy például a teljes gráfok komplementerei az ún. üres gráfok perfektek. Ugyanakkor könnyű mutatni olyan gráfcsaládot is, amelynek tagjai nem perfektek. Egy $n$ hosszú körön azt a $C_n$ gráfot értjük, amelynek csúcshalmaza $\{1,2,\ldots,n\}$ , az élhalmaza pedig $\{\{1,2\},\{2,3\},\ldots,\{n-1,n\},\{n,1\}\}$ . A 2. ábra bal oldalán lévő $G$ gráf például egy $C_5$ . Talán nem látszik elsőre, de gondoljuk meg, hogy a mellette lévő $\overline{G}$ is egy $C_5$ . Ha $n\ge 5$ páratlan egész, akkor $C_n$ nem perfekt gráf, hiszen a legnagyobb klikk mérete 2, míg a kromatikus száma 3. Amiből az is következik, hogy ha egy $G$ gráf tartalmaz feszített részgráfként egy páratlan kört⁶, akkor nem lehet perfekt. Ugyanígy könnyen belátható, hogy egy legalább 5 hosszú páratlan kör komplementere sem perfekt. (Ennek belátása jó gyakorló feladat lehet az olvasónak.)

Berge perfekt gráfokkal kapcsolatban az alább látható sejtéseket fogalmazta meg [2]. A perfekt gráf sejtés motivációjáról kicsit később lesz szó, de az erős perfekt gráf sejtés mögött álló gondolat már most nagyjából érthető: Berge azt vélte, hogy pontosan a (legalább 5 hosszú) páratlan körök és komplementereik, mint feszített részgráfok okoznak problémát a perfektség szempontjából. Tehát kizárt feszített részgráfok segítségével akarta karakterizálni a perfektséget.

Perfekt gráf sejtés (Berge, 1963). Egy gráf pontosan akkor perfekt, ha a komplementere is az.

Erős perfekt gráf sejtés (Berge, 1963). Egy gráf pontosan akkor perfekt, ha nem tartalmaz feszített részgráfként sem legalább 5 hosszú páratlan kört, sem legalább 5 hosszú páratlan kör komplementerét.

Lovász László a perfekt gráf sejtést bizonyította 1972-ben megjelent cikkében [15], amit mondjunk ki újra immár tételként:

Perfekt gráf tétel (Lovász, 1972 ⁷) Egy gráf pontosan akkor perfekt, ha a komplementere perfekt.

Egy másik, szintén 1972-ben megjelent dolgozatában [16] (Hajnal András javaslatára) egy tetszetős karakterizációját adta a perfektségnek, melynek következménye a perfekt gráf tétel.

Tétel (Lovász, 1972). Egy $G$ gráf pontosan akkor perfekt, ha

$\displaystyle \alpha(G') \omega(G') \ge \vert V(G')\vert$

teljesül minden $G'$ feszített részgráfjára.

Ez utóbbi tételnek könnyen láthatóan következménye a perfekt gráf tétel a „komplementer alak” miatt.

2. Előzmények, motiváció

Ebben a fejezetben arról lesz szó, hogy milyen korábbi eredmények motiválták Berge-t, milyen utak mentén lehet magáig a perfekt gráf fogalmáig és a sejtésig eljutni.

2.1. A „magyarabb” út

Berge számára jelentős insipirációt jelentettek egyes páros gárfokra vonatkozó kombinatorikai min-max tételek, így az egyik úthoz nagyon sok magyar matematikus neve kapcsolódik. Ezen eredmények bemutatásához be kell vezetnünk egy új gráfparamétert, és vissza kell mennünk az időben egészen Kőnig Dénes minden alapozó kurzus anyagában szereplő tételéig.

Egy gráfot párosnak mondunk, ha a csúcshalmazát fel tudjuk bontani két diszjunkt részhalmazra úgy, hogy a részeken belül nincs a gráfnak éle (azaz az eddigi foglalmakkal: két diszjunkt, független részhalmazra tudjuk bontani). Könnyű látni, hogy $\omega(G)=\chi(G)$ minden páros gráfra teljesül. Egy $E \subseteq E(G)$ halmazt lefogó élhalmaznak mondunk, ha minden csúcsot „lefog” $G$ -ben, azaz nincs olyan csúcs a gráfban, amely ne lenne valamely $E$ -beli él végpontja. A lefogó élek minimális számát $G$ -ben $\rho(G)$ jelöli. Egy csúcsot izoláltnak mondunk, ha nincs olyan él a gráfban, amelynek végpontja lenne.

Tétel (Kőnig Dénes, 1931, [14]). Egy izolált csúcs nélküli $G$ páros gráfra teljesül, hogy $\alpha(G)=\rho(G)$ .

Ennek az eredménynek röviden vázolom egy következményét, mégpedig azt, hogy (izolált pont nélküli) $G$ páros gráfban $\alpha(G)=\chi(\overline{G})$ . (Mivel $\alpha(G)=\omega(\overline{G})$ , ezért ez úgy is írható, hogy $\omega(\overline{G})=\chi(\overline{G})$ .)

Vizsgáljuk meg Kőnig tételét, és vegyünk egy $\alpha(G)(=\rho(G))$ nagyságú $E$ lefogó élhalmazt az izolált pont nélküli $G$ páros gráfban. Ezen $E$ -beli élek olyanok, hogy egyrészt legfeljebb egy csúcsot tartalmazhatnak egy $\alpha(G)$ nagyságú független $X$ halmazból, másrészt minden csúcsot tartalmaznak $G$ -ből, mint végpont. Sőt, az ún. Hall-tétel⁸ segítségével azt is elérhetjük, hogy az $X$ -en kívüli pontokat bepárosíthatjuk $X$ -be, azaz minden $X$ -en kívüli ponthoz hozzárendelhetünk egy saját, külön $X$ -beli szomszédot. Ha észrevételeinket $G$ komplementerére lefordítjuk, akkor ott $X$ egy teljes részgráfot fog feszíteni és minden $X$ -en kívüli $G$ -beli csúcshoz lesz hozzárendelve egy olyan pont $X$ -ben, mellyel nem lesz összekötve (és minden $X$ -en kívülihez más és más $X$ -beli lesz így hozzárendelve). Na de akkor $G$ komplementerének kromatikus száma $\vert X\vert=\alpha(G)$ . Hiszen egyrészt legalább ennyi szín kell a színezéséhez, másrészt minden $X$ -en kívüli pontot színezzünk annak a (saját) pontjának a színével, akihez „nincs hozzákötve” $\overline{G}$ -ben. Tehát megkaptuk, amit szerettünk volna: izolált pont nélküli $G$ páros gráfban $\alpha(G)=\chi(\overline{G})$ . Annak végiggondolását, hogy az izolált pont nem okoz gondot, és minden $G$ páros gráfban $\alpha(G)=\chi(\overline{G})$ , az olvasóra bízzuk.

Kőnig Dénes egy másik, ún. élszínezési tételéből következik, hogy egy $G$ páros gráf $L(G)$ élgráfjára teljesülnek az $\omega(L(G))=\chi(L(G))$ és $\alpha(L(G))=\chi(\overline{L(G)})$ egyenlőségek. (Egy $G$ élgráfja az az $L(G)$ gráf, aminek a csúcsai $G$ éleinek felelnek meg, és két csúcsa pontosan akkor van éllel összekötve, ha az eredeti $G$ gráfban a két élnek volt közös végpontja.) Ezen kezdetek után egyre több gráfosztályra láttak be olyan típusú tételeket, hogy az osztályhoz tartozó $G$ gráfokra $\omega(G)=\chi(G)$ és $\alpha(G)=\chi(\overline{G})$ teljesül. Meg is említunk néhány példát.

$\bullet$ Olyan gráfokat hívunk intervallumgráfnak, amelyek csúcsai megfeleltethetőek a valós számok egy-egy intervallumának, és két csúcs között pontosan akkor van él, ha a megfelelő intervallumok metszete nem üres. A fogalmat Hajós György vezette be [13]-ben, ahol egyből belátta, hogy $\omega(G)=\chi(G)$ fennáll intervallumgráfokra. Később Gallai Tibor látta be, hogy $\alpha(G)=\chi(\overline{G})$ is igaz.

4. ábra. Egy intervallumgráf

$\bullet$ Azt mondjuk, hogy egy gráfban minden kör háromszögelt, ha nincsen benne feszített, legalább 4 hosszú kör⁹. Ilyen típusú gráfokra Berge látta be [1], hogy $\omega(G)=\chi(G)$ , valamint Hajnal András és Surányi János látták be [12], hogy $\alpha(G)=\chi(\overline{G})$ . Később Gallai Tibor [10] ez utóbbi eredményt erősítette és belátta, hogy elegendő feltenni, hogy minden legalább 5 hosszú páratlan körben van 2 „egymást nem metsző” átló¹⁰ ahhoz, hogy tudjuk $\alpha(G)=\chi(\overline{G})$ . Ennek az eredménynek később egy rövidebb bizonyítását adta Surányi László [23].

Azt láttuk, hogy magyar matematikusok aktív részvételével létrejöttek olyan tételek, amelyek azt mondják ki, hogy mind $\omega(G)=\chi(G)$ mind $(\omega(\overline{G})=)\alpha(G)=\chi(\overline{G})$ igaz bizonyos gráfosztályokban. Annak az észrevételnek az ellenőrzését az olvasóra bízzuk, hogy a fent említett gráfosztályok mind olyanok, amelyek zártak a feszített részgráfok képzésére, és máris megkapjuk a perfekt gráf sejtés egyik motivációját.

2.2. A másik út: Shannon kapacitás

Berge számára a másik fontos motivációt Claude Shannon 1956-ban megjelent cikke [20] jelentette, amiben bevezeti a Shannon kapacitás fogalmát¹¹.

Az alapfeladatban adott egy ábécé (ennek elemeit egy $G$ gráf $V(G)$ csúcshalmazával reprezentáljuk), amelyben bizonyos betűk összetéveszthetők egymással (az összetéveszthető betűpárok alkotják a gráf $E(G)$ élhalmazát). Az ábécé betűiból készített két azonos hosszúságú szót összetéveszthetőnek nevezünk, ha minden pozícióban azonos vagy összetéveszthető betűk állnak. A kérdés, hogy legfeljebb hány $t$ hosszú szót tudunk úgy készíteni, hogy semelyik kettő ne legyen egymással összetéveszthető? Ez a szám $t$ -ben exponenciálisan nő, és azt a mennyiséget, ahová ezeknek a számoknak a $t$ -edik gyöke tart¹² a $G$ gráf Shannon kapacitásának nevezzük és $\Theta(G)$ -vel jelöljük. Rövid vizsgálódás után $\Theta(G)$ -re a következő egyenlőtlenségek adódnak:

$\displaystyle \alpha(G) \le \Theta(G) \le \chi(\overline{G}).$

Shannon [20]-ban meghatározta minden legfeljebb 4-csúcsú gráf Shannon kapacitását és az 5-csúcsúakét is egy kivétellel, majd két kérdést tett fel:

1. kérdés Mik azok a minimális gráfok, amelyekre $\Theta(G) \neq \alpha(G)$ ?

2. kérdés Mennyi $\Theta(C_5)$ ?

Az első kérdés jól mutatja az $\alpha(G)=\chi(\overline{G})$ egyenlőség jelentőségét, ugyanis ha az fennáll, akkor a $\Theta(G)=\alpha(G)$ is teljesül. Nagyon röviden ez volt a második motiváció, aminek mentén Berge eljutott a perfekt gráfok fogalmához. Míg a második kérdést azért is fontos kiemelni, mert azt is Lovász László válaszolta meg [17]-ben.

A fent leírt két útnak köszönhetően talán az olvasó is kaphatott egy képet arról, hogy hogyan épülnek egymásra az eredmények, és hogy léteznek közös motivációk a háttérben.

2.3. Berge gráfosztályai

A motivációkat és előzményeket bemutató részt Berge gráfosztályaival zárjuk:

1. osztály: olyan $G$ gráfok, amelyekre $\Theta(G)=\alpha(G)$ .

2. osztály: olyan $G$ gráfok, amelyekre $\alpha(G')= \chi(\overline{G'})$ teljesül minden $G'$ feszített részgráfjára $G$ -nek. ¹³

3. osztály: olyan $G$ gráfok, amelyekre $\omega(G') = \chi(G')$ teljesül minden $G'$ feszített részgráfjára $G$ -nek.

4. osztály: olyan $G$ gráfok, amelyek nem tartalmaznak sem legalább 5 hosszú páratlan kört, sem azok komplementerét, mint feszített részgráfot.

Egy 1960-ban tartott szemináriumon Berge azt a kérdést tette fel, hogy igaz-e, hogy a 4. osztályban lévő gráfok az 1. osztályban is benne vannak? Míg 1963-as dolgozatában [2] a következőket kérdezte:

3. kérdés Igaz-e, hogy a 2. osztály és a 3. osztály ugyanazokat a gráfokat tartalmazza?

4. kérdés Igaz-e hogy a 3. osztály és a 4. osztályban ugyanazok a gráfok vannak?

Ezek a kérdések már ismerősök lehetnek:

$\bullet$ Ha a 2. osztály és a 3. osztály elemei megegyeznek, az az $\alpha(G')=\omega(\overline{G'})$ összefüggés miatt épp azt jelenti, hogy egy gráf pontosan akkor perfekt, ha a komplementere perfekt. Tehát itt a perfekt gráf sejtést látjuk.

$\bullet$ Ha a 3. osztály egybeesik a 4. osztállyal, az pedig azt jelenti, hogy pontosan azok a gráfok perfektek, amelyek sem legalább 5 hosszú páratlan kört, sem azok komplementerét nem tartalmazzák, mint feszített részgráfot. Ez pedig maga az erős perfekt gráf sejtés.

Ez volt a perfekt gráfok, a perfekt gráf sejtés, valamint az erős perfekt gráf sejtés keletkezésének zanzásított története. Amit meg szerettem volna mutatni, és valamennyire fel akartam idézni, az az, hogy hány különböző terület képviselőit érdekelt a sejtés, és hogy mennyire centrális szerepe volt a megoldásnak a '70-es évek elején. Akinek esetleg sikerült felkelteni az érdeklődését a perfekt gráfok (és történetük) iránt (és nem ismeri a vonatkozó irodalmat), annak melegen ajánljuk Berge [3] cikkét, illetve annak kiegészített újraközlését [4], amelyben kimerítő, szinte hónapról hónapra leírt történettel szolgál arról, hogy hogyan merült fel a fogalom, hogyan születtek, majd konferenciáról konferenciára közvetítődtek a perfekt gráfokkal kapcsolatos eredmények az '50-es évek végén és a '60-as években.

3. Néhány szó a bizonyításról és az utóbbi évtizedek eredményeiről

Természetesen a bizonyítás teljes ismertetése túlfeszítené a cikk kereteit, így csak egy lényeges dolgot említünk meg nagyon röviden. Lovász László (először megjelent, azaz [15]-beli) bizonyításának fő összetevője az ún. többszörözési lemma volt. A többszörözési lemma azt mondja, hogy ha egy perfekt gráf egy $v$ pontját egy teljes gráffal helyettesítjük abban az értelemben, hogy a teljes gráf minden pontja a $v$ eredeti szomszédaival van öszekötve, akkor perfekt gráfot kapunk. Ennek a lemmának a segítségével lehetett eljutni a Fulkerson [9] által megkezdett úton a sejtés bizonyításáig. (Megjegyezzük, hogy a perfekt gráf tételre manapság a legtöbb helyen egy Gaspariantól [11] származó bizonyítás „van forgalomban”.)

Akit jobban érdekel a téma és a legújabb fejlemények, annak ajánlom Schrijver monográfiájának [21] megfelelő fejezeteit, valamint a Ramírez Alfonsín és Reed által szerkesztett kötetet [19]. Két áttörést feltétlenül ki kell még emelnünk. Egyrészt azóta kiderült, hogy polinom időben el lehet dönteni, hogy egy gráf perfekt-e [5,8]. Másrészt – utolsó mondatként – kerüljön ide, hogy a Chudnovsky–Robertson–Seymour–Thomas szerzőnégyesnek 2003-ban sikerült belátni az erős perfekt gráf sejtést [6,7].

Irodalomjegyzék

: [1] C. Berge. Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind. Wissenschaftliche Zeitschrift Martin Luther Univ. Halle-Wittenberg, 10 (1961), 114–115.

[2] C. Berge. Some classes of perfect graphs. Six Papers on Graph Theory. (related to a series of lectures at the Research and Training School of the Indian Statistical Institute, Calcutta, 1963) 1–21.

[3] C. Berge. Motivations and history of some of my conjectures. Discrete Mathematics, 165 (1997), 61–70.

[4] C. Berge, J. R. Ramírez Alfonsin. Origins and genesis. In: Perfect graphs, Wiley, 44, (2001), 1–12.

[5] M. Chudnovsky, G. Cornuéjols, X. Liu, P. Seymour, K. Vušković, Recognizing berge graphs. Combinatorica, 25(2) (2005), 143–186.

[6] M. Chudnovsky, N. Robertson, P. D. Seymour, R. Thomas. The strong perfect graph theorem. Annals of Mathematics, (2006), 51–229.

[7] M. Chudnovsky, N. Robertson, P.D. Seymour, R. Thomas. Progress on perfect graphs. Mathematical Programming, 97(1) (2003), 405–422.

[8] G. Cornuéjols, X. Liu, K. Vuskovic. A polynomial algorithm for recognizing perfect graphs. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. (pp. 20–27). IEEE.

[9] D. R. Fulkerson. Anti-blocking polyhedra. Journal of Combinatorial Theory, Series B, 12(1) (1972), 50–71.

[10] T. Gallai. Graphen mit triangulierbaren ungeraden Vielecken. Magyar Tud. Akad. Mat. Kutato Int. Közl. 7 (1962), 3–36.

[11] G. S. Gasparian. Minimal imperfect graphs: a simple approach. Combinatorica, 16(2) (1996), 209–212.

[12] A. Hajnal, J. Surányi. Über die Auflösung von Graphen in vollständige Teilgraphen. Ann. Univ. Sci. Budapest, Eötvös Sect. Math., 1 (1958), 113–121.

[13] Gy. Hajós. (problem 65) Über eine art von graphen. Internationale Mathematische Nachrichten, 11, 1957.

[14] D. Kőnig. Gráfok és mátrixok. Matematikai és Fizikai Lapok, 38 (1931), 116–119.

[15] L. Lovász. Normal hypergraphs and the perfect graph conjecture. Discrete Mathematics, 2(3) (1972), 253–267.

[16] L. Lovász. A characterization of perfect graphs. Journal of Combinatorial Theory, Series B, 13(2) (1972), 95–98.

[17] L. Lovász. On the Shannon capacity of a graph. IEEE Transactions on Information theory, 25(1) (1979), 1–7.

[18] J. Mycielski. Sur le coloriage des graphes, Colloq. Math., 3 (1955), 161–162.

[19] J. L. Ramírez-Alfonsín, B. A. Reed. Perfect graphs (Vol. 44). Wiley, 2001.

[20] C. Shannon. The zero error capacity of a noisy channel. IRE Transactions on Information Theory, 2(3) (1956), 8–19.

[21] A. Schrijver. Combinatorial optimization: polyhedra and efficiency (Vol. 24). Springer Science & Business Media, 2003.

[22] T. B. Schwarcz. Gráfok Shannon kapacitása, MSc dolgozat, ELTE, 2018.

[23] L. Surányi. The covering of graphs by cliques, Stud. Sci. Math. Hungar 3 (1968), 345–349.

Lábjegyzetek

: ¹ Egy másik lehetséges definíciója a feszített részgráfnak, hogy -ből csúcsokat (és hozzájuk tartozó éleket) hagyunk el.
: ² Izomorfián olyan bijekciót értünk 2 gráf csúcshalmaza között, amely élt élbe és nem élt nem élbe visz.
: ³ Szokták stabil csúcshalmaznak is hívni.
: ⁴ Ugyan nem tartozik szorosan a cikk témájához, de felmerülhet az olvasóban a kérdés, hogy vajon $\chi(G)$ -t tudjuk-e $\omega(G)$ valamilyen függvényével felülről is becsülni. A meglepő valász az, hogy nem: Mycielski [18] bizonyította, hogy minden $k \ge 2$ egész számhoz létezik olyan gráf, melyre $\omega(G_k)=2$ és $\chi(G_k)=k$ .
: ⁵ francia matematikus, 1926–2002
: ⁶ A feszített kört angolul hole-nak, magyarul üregnek is mondják néhol a szakirodalomban, mi a „kört feszített részgráfként” terminust fogjuk használni.
Érdekesség, hogy Berge semi Gallai gráfoknak hívta a páratlan kört feszített részgráfként nem tartalmazó gráfokat, ami ellen Gallai tiltakozott, így Berge megváltoztatta a fogalom nevét.
: ⁷ Tételekhez a cikk megjelenésének évét szokták odaírni, de a bizonyítás 1971-ben született.
: ⁸ A Hall-tétel vagy angolul Hall's marriage theorem arra ad szükséges és elégséges feltételt, hogy egy páros gráfban a csúcshalmaz egyik osztálya mikor „párosítható be” a másik osztályba.
: ⁹ Annak kitalálását, hogy honnan jöhet a háromszögeltség elnevezés, és mi lehet egy, a nevet jobban tükröző ekvivalens definíció, az olvasóra bízzuk.
: ¹⁰Ami ekvivalens azzal, hogy bármely legalább 5 hosszú páratlan kör háromszögelt.
: ¹¹June 1957: When he heard that I was writing a book on graph theory, my friend M.P. Schutzenberger drew my attention on an interesting paper of Shannon which was presented at a meeting for engineers and statisticians, but which could have been missed by mathematicians working in algebra or combinatorics. (idézet [3,4] )
: ¹²Hogy valóban létezik ez a határérték, illetve részletesebb leírásokért lásd például [22]
: ¹³Itt $\overline{G'}$ a csúcshalmazra vonatkoztatott komplementere -nek.