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:
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.
Világos, hogy ha egy él kritikus elem, akkor végpontjai is azok. Többet nem állíthatunk: Hárompontú fának 2-fokú csúcsa kritikus, de a rá illeszkedő élek nem. Emellett legyenek egy gráf csúcsai egy szabályos hétszög csúcsai, élei pedig a hétszög átlói. E gráfnak minden csúcsa kritikus, noha élei nem mind azok.
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 összefüggő. Szétvágó csúcshalmaza nem feszít ki teljes részgráfot. Két speciális eset: egyrészt nem tartalmaz szétvágó csúcsot, másrészt ha van benne szétvágó csúcspár, akkor e két csúcs nem szomszédos. G véges (ez a de Bruijn–Erdős-tétel: ). δ(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 Ha G (k − 1)-reguláris, tehát minden csúcs pontosan k − 1 csúccsal szomszédos, akkor G vagy a Kk vagy egy páratlan kör. Ez a Brooks-tétel; lásd ). 2 m ≥ (k − 1) n + k − 3 . 2 m ≥ (k − 1) n + [(k − 3)/(k2 − 3)] n . 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 . 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 .
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.
alapján minden k-kritikus gráf előállítható a Kk 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 Kk teljes gráfon kívül létezik-e más duplakritikus k''-kromatikus számú gráf .
Kapcsolódó szócikkek Faktorkritikus gráf
Fordítás
Jegyzetek
. . (Indag. Math. 13.) . . . . . . . .
További információk ELTE jegyzet a színezésekről
Kategória:Gráfcsaládok Kategória:Gráfok színezése