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

• Tényezőkritikus grafikon

Jegyzetek

1. ↑ 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 )
2. ↑ de Bruijn, Erdős, 1951 .
3. ↑ Lovász, 1992 .
4. ↑ Brooks, Tutte, 1941 .
5. ↑ Dirac, 1957 .
6. ↑ Gallai, 1963a .
7. ↑ Gallai, 1963b .
8. ↑ Stehlik, 2003 .
9. ↑ Harari, 2003 , p. 167.
10. ↑ Hajos, 1961 .
11. ↑ Harari, 2003 , p. 168-169.
12. ↑ 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.