Kritikus grafikon
A kritikus gráf olyan gráf , amelyben bármely csúcs vagy él eltávolítása csökkenti a gráf
kromatikus számát .
Kapcsolódó definíciók
A -kritikus gráf egy k kromatikus számú kritikus gráf .
- Egy k kromatikus számú G gráf csúcs - k -kritikus , ha minden csúcsa kritikus elem [1] .
Tulajdonságok
- Legyen G egy k -kritikus gráf n csúcsgal és m éllel. Akkor:
- G -nek csak egy komponense van .
- G véges ( de Bruijn-Erdős tétel [2] ).
- δ( G ) ≥ k − 1, azaz bármely csúcs legalább k − 1 másik csúcs szomszédos. Pontosabban, G ( k − 1)-él-összefüggés [3] .
- Ha a G gráf ( k − 1)-szabályos (minden csúcs pontosan k − 1 másikkal szomszédos), akkor a G gráf vagy egy teljes K k gráf , vagy egy páratlan ciklus . (Ez Brooks tétele [4] ).
- 2 m ≥ ( k − 1) n + k − 3 [5] .
- 2 m ≥ ( k − 1) n + [( k − 3)/( k 2 − 3)] n [6] .
- G két kisebb kritikus gráfra bontható, ahol az egyes csúcspárok között van egy él, ahol két csúcs különböző részekből származik, vagy G - nek legalább 2k - 1 csúcsa van [7] . Pontosabban, vagy G -nek vannak ilyen típusú dekompozíciói, vagy a G gráf minden v csúcsához van egy k színezés, amelyben v az egyetlen csúcs, amelynek saját színe van, és minden más színosztálynak legalább két csúcsa van [8 ] .
- Egy G gráf akkor és csak akkor csúcskritikus, ha bármely v csúcshoz létezik optimális megfelelő színezés, amelyben a v csúcs önmagában képviseli a színosztályt.
- 1-kritikus gráfok nem léteznek.
- Az egyetlen 2-kritikus gráf a K 2 .
- Minden 3-kritikus gráfot kimerítenek páratlan hosszúságú egyszerű ciklusok [9] .
- Ahogy Hajos [10] megmutatta , bármely k - kritikus gráf létrehozható egy teljes K k gráfból, ha a Hajos konstrukcióját kombináljuk két nem szomszédos csúcs azonosításának műveletével. Az így kialakított gráf mindig k színt igényel bármilyen megfelelő színezésben.
- Bár minden vonalkritikus gráf szükségszerűen kritikus, ennek ellenkezője nem igaz. Például a jobb oldali gráf 4-kritikus, de nem élkritikus [11] .
Változatok és általánosítások
- A duplán kritikus gráf olyan összefüggő gráf, amelyben bármely szomszédos csúcspár eltávolítása kettővel csökkenti a kromatikus számot. Az egyik megoldatlan probléma, hogy K k -e az egyetlen kétszeresen kritikus k - kromatikus gráf [12] .
Lásd még
Jegyzetek
- ↑ Megjegyzendő, hogy a kritikus gráf nem mindig kritikus k -kromatikus gráf. Viizing cikkében a k dimenziójú kritikus gráf alatt olyan gráfot értünk, amelynek bármely sajátrészének mérete kisebb, mint k. Ebben az esetben a gráf dimenziója alatt a metrikus tér azon minimális méretét értjük, amelybe a gráf beágyazható úgy, hogy az összes szomszédos csúcs 1 távolságra legyen. ( Vizing 1968 )
- ↑ de Bruijn, Erdős, 1951 .
- ↑ Lovász, 1992 .
- ↑ Brooks, Tutte, 1941 .
- ↑ Dirac, 1957 .
- ↑ Gallai, 1963a .
- ↑ Gallai, 1963b .
- ↑ Stehlik, 2003 .
- ↑ Harari, 2003 , p. 167.
- ↑ Hajos, 1961 .
- ↑ Harari, 2003 , p. 168-169.
- ↑ Erdős, 1966 .
Irodalom
- R. L. Brooks, W. T. Tutte. Egy hálózat csomópontjainak színezéséről // Proceedings of the Cambridge Philosophical Society. - 1941. - T. 37 , sz. 02 . – S. 194–197 . - doi : 10.1017/S030500410002168X .
- N. G. de Bruijn , P. Erdős . Színprobléma végtelen gráfokhoz és probléma a relációelméletben // Nederl. Akad. Wetensch. Proc. Ser. A. - 1951. - T. 54 . – S. 371–373 . . ( Indag. Matek. 13.)
- GA Dirac. RL Brooks tétele és H. Hadwiger sejtése // Proceedings of the London Mathematical Society. - 1957. - T. 7 , sz. 1 . – S. 161–195 . - doi : 10.1112/plms/s3-7.1.161 .
- T. Gallai. Kritische Graphen I // Publ. Math. Inst. magyarország. Acad. Sc.. - 1963a. - T. 8 . – S. 165–192 .
- T. Gallai. Kritische Graphen II // Publ. Math. Inst. magyarország. Acad. Sc.. - 1963b. - T. 8 . – S. 373–395 . .
- G. Hajos . Uber eine Konstruktion nicht n -färbbarer Graphen // Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe. - 1961. - T. 10 . – S. 116–117 .
- TR Jensen, B. Toft. Grafikonszínezési problémák. - New York: Wiley-Interscience, 1995. - ISBN 0-471-02865-7 .
- Matj Stehlik. Kritikus gráfok kapcsolódó komplementerekkel // Journal of Combinatorial Theory . - 2003. - T. 89 , sz. 2 . – S. 189–194 . - doi : 10.1016/S0095-8956(03)00069-8 .
- Lovasz László . Kombinatorikus problémák és gyakorlatok (második kiadás). – Észak-Hollandia, 1992.
- Erds Pál . A gráfok elméletében. — Proc. Kollok., Tihany, 1966. - 361. o.
- V. G. Vizing. Néhány megoldatlan probléma a gráfelméletben // Uspekhi Matematicheskikh Nauk. - 1968. - T. XXIII , sz. 6 (144) . – 117–134 .
- F. Harari. Gráfelmélet. - 2. - M. : Szerkesztői URSS, 2003. - ISBN 5-354-00301-6 , BBC 22.144, 22.18, 22.19.