| dbo:abstract
|
- 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. 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: ).
* δ(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 é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 . (hu)
- 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. 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: ).
* δ(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 é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 . (hu)
|
