Kritický graf - Critical graph

Vlevo nahoře vrcholový kritický graf s chromatickým číslem 6; dále všechny podgrafy N-1 s chromatickým číslem 5.

v teorie grafů, a kritický graf je graf G ve kterém je každý vrchol nebo hrana a kritický prvek, tj. pokud jeho odstranění sníží chromatické číslo z G. Takový pokles nemůže být o více než 1.

Variace

A k-kritický graf je kritický graf s chromatickým číslem k; graf G s chromatickým číslem k je k-vertex-critical pokud je každý z jeho vrcholů kritickým prvkem. Kritické grafy jsou minimální členů, pokud jde o chromatické číslo, což je velmi důležité měřítko v teorii grafů.

Některé vlastnosti a k-kritický graf G s n vrcholy a m hrany:

G má jen jednu součástka.
G je konečný (to je de Bruijn – Erdősova věta z de Bruijn & Erdős 1951 ).
δ (G) ≥ k - 1, to znamená, že každý vrchol sousedí alespoň s k - 1 další. Silněji, G je (k − 1)-připojeno k okraji. Vidět Lovász (1992)
Li G je (k - 1) -pravidelné, což znamená, že každý vrchol přesně sousedí k - 1 další, tedy G je buď K._k nebo lichý cyklus . Tohle je Brooksova věta; vidět Brooks & Tutte (1941) ).
2 m ≥ (k − 1) n + k − 3 (Dirac 1957 ).
2 m ≥ (k − 1) n + [(k − 3)/(k² − 3)] n (Gallai 1963a ).
Buď G mohou být rozloženy na dva menší kritické grafy, s hranou mezi každou dvojicí vrcholů, která zahrnuje jeden vrchol z každého ze dvou podgrafů, nebo G má alespoň 2k - 1 vrcholy (Gallai 1963b ). Ještě silněji G má rozklad tohoto typu, nebo pro každý vrchol proti z G tady je k-barvení, ve kterém proti je jediný vrchol své barvy a každá další barevná třída má alespoň dva vrcholy (Stehlík 2003 ).

Graf G je kritický pro vrcholy právě tehdy, když pro každý vrchol proti, existuje optimální správné zbarvení, ve kterém proti je singletonová barevná třída.

Tak jako Hajós (1961) ukázal, každý k-kritický graf může být vytvořen z a kompletní graf K._k kombinací Hajósova konstrukce s operací, která identifikuje dva nesousedící vrcholy. Takto vytvořené grafy vždy vyžadují k barvy v jakémkoli správném zbarvení.

A dvojkritický graf je připojený graf, ve kterém odstranění jakékoli dvojice sousedních vrcholů snižuje chromatické číslo o dva. Jedním z otevřených problémů je určit, zda K._k je jedinou dvojitou kritikou k-chromatický graf.^[1]

Viz také

Faktorově kritický graf

Reference

^ Erdős 1967.

Zdroje

Brooks, R.L .; Tutte, W. T. (1941), „O vybarvení uzlů sítě“, Sborník Cambridge Philosophical Society, 37 (02): 194–197, doi:10.1017 / S030500410002168X
de Bruijn, N. G.; Erdős, P. (1951), „Barevný problém pro nekonečné grafy a problém v teorii vztahů“, Nederl. Akad. Wetensch. Proc. Ser. A, 54: 371–373. (Indag. Matematika. 13.)
Dirac, G. A. (1957), „Věta R. L. Brookse a domněnka o H. Hadwigerovi“, Proceedings of the London Mathematical Society, 7 (1): 161–195, doi:10.1112 / plms / s3-7.1.161
Erdős, Paul (1967), "Problém 2", V teorii grafů, Proc. Colloq., Tihany, str. 361CS1 maint: ref = harv (odkaz)
Gallai, T. (1963a), „Kritische Graphen I“, Publ. Matematika. Inst. Hungar. Acad. Sci., 8: 165–192
Gallai, T. (1963b), „Kritische Graphen II“, Publ. Matematika. Inst. Hungar. Acad. Sci., 8: 373–395
Hajós, G. (1961), „Über eine Konstruktion nicht $n$ -färbbarer Graphen ", Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, 10: 116–117.
Jensen, T. R .; Toft, B. (1995), Problémy s barvením grafů, New York: Wiley-Interscience, ISBN 0-471-02865-7
Stehlík, Matěj (2003), „Kritické grafy s připojenými doplňky“, Journal of Combinatorial Theory, Řada B, 89 (2): 189–194, doi:10.1016 / S0095-8956 (03) 00069-8, PAN 2017723.
Lovász, László (1992), „Řešení cvičení 9.21“, Kombinatorické problémy a cvičení (druhé vydání), Severní Holandsko
Stiebitz, Michael; Tuza, Zsolt; Voigt, Margit (6. srpna 2009), "V seznamu kritických grafů", Diskrétní matematika, Elsevier, 309 (15): 4931–4941, doi:10.1016 / j.disc.2008.05.021

[FOOTNOTEErdős1967-1] Erdős 1967.

[1]