Kritikus gráf

A kritikusság általánosságban bármilyen tulajdonságra vagy mértékre utalhat. A gráfelmélet területén a kifejezést szinte mindig egy gráf kromatikus számával kapcsolatban használjuk. A kritikus gráfok érdekességét az adja, hogy a gráfelméletileg fontos tulajdonság, a kromatikus szám szempontjából minimálisak. Precízebben:

Baloldalt felül egy 6 kromatikus számú csúcskritikus gráf található; a többi gráf ennek N−1 részgráfja, 5 kromatikus számmal.

Egy G gráf csúcsa vagy éle a gráf kritikus eleme, ha törlésével G kromatikus száma csökkenne. Nyilvánvalóan a csökkenés legfeljebb 1-gyel történhet.

Egy kritikus gráf olyan gráf, melynek minden csúcsa vagy éle kritikus elem. Egy k-kritikus gráf olyan kritikus gráf, aminek kromatikus száma k; ha egy k kromatikus számú G gráf minden csúcsa kritikus elem, akkor a gráf k-csúcskritikus, ha pedig egy k élkromatikus számú (kromatikus indexű) gráf minden éle kritikus elem, akkor a gráf k-élkritikus.

Az n csúccsal és m éllel rendelkező k-kritikus G gráfok néhány tulajdonsága:

• G egyetlen komponensből áll.
• G véges (ez a de Bruijn–Erdős-tétel: de Bruijn & Erdős 1951).
• δ(G) ≥ k − 1, tehát minden csúcs legalább k − 1 csúccsal szomszédos. Ami ennél erősebb G (k − 1)-szeresen élösszefüggő. Lásd (Lovász 1992)
• Ha G (k − 1)-reguláris, tehát minden csúcs pontosan k − 1 csúccsal szomszédos, akkor G vagy a K_k vagy egy páratlan kör. Ez a Brooks-tétel; lásd (Brooks & Tutte 1941)).
• 2 m ≥ (k − 1) n + k − 3 (Dirac 1957).
• 2 m ≥ (k − 1) n + [(k − 3)/(k² − 3)] n (Gallai 1963a).
• G vagy felbontható két kisebb kritikus gráfra, ahol minden csúcsot a másik részgráf minden csúcsával él köti össze, vagy G-nek legalább 2k − 1 csúcsa van (Gallai 1963b). Ennél erősebb állítás is igaz: G vagy felbontható az előbbi módon, vagy G minden v csúcsához tartozik olyan k-színezés, amiben v színe nem szerepel más csúcsnál, minden más színosztályba pedig legalább két csúcs tartozik (Stehlík 2003).

Könnyen belátható, hogy G pontosan akkor csúcskritikus, ha minden v csúcsához tartozik egy optimális, jó színezése, melyben v egyelemű színosztály.

(Hajós 1961) alapján minden k-kritikus gráf előállítható a K_k teljes gráfból a Hajós-konstrukció és a két nem szomszédos csúcs azonosításának művelete segítségével. Az így megalkotott gráfok jó színezéséhez mindig legalább k színre van szükség.

Egy kétszeresen kritikus gráf vagy duplakritikus gráf (double-critical graph) olyan összefüggő gráf, melyben bármely két szomszédos csúcs törlése a kromatikus számot kettővel csökkenti. Nyitott kérdés, hogy a K_k teljes gráfon kívül létezik-e más duplakritikus k-kromatikus számú gráf (Erdős 1966).

Kapcsolódó szócikkek

• Faktorkritikus gráf

Fordítás

• Ez a szócikk részben vagy egészben a Critical graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

• .
• . (Indag. Math. 13.)
• .
• .
• .
• .
• .
• .
• .
• .

További információk

• ELTE jegyzet a színezésekről