Kriittinen kaavio

Kriittinen graafi  on graafi , jossa minkä tahansa kärjen tai reunan poistaminen vähentää graafin kromaattista lukumäärää .

Aiheeseen liittyvät määritelmät

• -kriittinen graafi  on kriittinen graafi, jonka kromaattinen luku k .
• Graafi G , jonka kromaattinen luku on k , on piste - k -kriittinen , jos jokainen sen kärkipiste on kriittinen elementti [1] .

Ominaisuudet

• Olkoon G k -kriittinen graafi, jossa on n kärkeä ja m reunaa. Sitten:
  • G :ssä on vain yksi komponentti .
  • G on äärellinen ( de Bruijn-Erdősin lause [2] ).
  • δ( G ) ≥ k − 1, eli mikä tahansa kärki on vähintään k  − 1 muun kärjen vieressä. Tarkemmin sanottuna G on ( k  − 1)-reunakytketty [3] .
  • Jos kuvaaja G on ( k  − 1)-säännöllinen (jokainen kärki on täsmälleen k  − 1 muun vieressä ), graafi G on joko täydellinen graafi K k tai pariton jakso . (Tämä on Brooksin lause [4] ).
  • 2 m ≥ ( k − 1) n + k − 3 [5] .
  • 2 m ≥ ( k − 1) n + [( k − 3)/( k 2 − 3)] n [6] .
  • Joko G voidaan jakaa kahdeksi pienemmäksi kriittiseksi graafiksi, joissa on reuna kunkin pisteparin välissä, jossa kaksi pistettä tulee eri osista, tai G :llä on vähintään 2k  - 1 pistettä [7] . Tarkemmin sanottuna joko G :llä on tämän tyyppisiä hajotuksia tai jokaiselle graafin G kärjelle v on k -väritys, jossa v on ainoa piste, jolla on oma väri, ja kaikilla muilla väriluokilla on vähintään kaksi kärkeä [8 ] .

• Graafi G on kärkikriittinen silloin ja vain, jos jollekin pisteelle v on olemassa optimaalinen sopiva väritys, jossa kärki v yksin edustaa väriluokkaa.

• 1-kriittisiä kaavioita ei ole olemassa.
• Ainoa 2-kriittinen graafi on K 2 .
• Kaikki 3-kriittiset graafit tyhjennetään yksinkertaisilla parittoman pituisilla sykleillä [9] .

• Kuten Hajos [10] osoitti , mikä tahansa k -kriittinen graafi voidaan muodostaa täydellisestä graafista K k yhdistämällä Hajosin konstruktio kahden ei-viereisen kärjen tunnistamisoperaatioon. Tällä tavalla muodostettu graafi vaatii aina k väriä missä tahansa asianmukaisessa värjäyksessä.

• Vaikka jokainen viivakriittinen graafi on välttämättä kriittinen, päinvastoin ei pidä paikkaansa. Esimerkiksi oikealla oleva kaavio on 4-kriittinen, mutta ei reunakriittinen [11] .

Muunnelmia ja yleistyksiä

• Kaksoiskriittinen graafi on yhdistetty graafi, jossa minkä tahansa vierekkäisten kärkien parin poistaminen vähentää kromaattista lukua kahdella. Yksi ratkaisemattomista ongelmista on, onko K k ainoa kaksoiskriittinen k - kromaattinen graafi [12] .

Katso myös

• Tekijäkriittinen kaavio

Muistiinpanot

1. ↑ On huomattava, että kriittinen graafi ei aina ymmärretä kriittistä k -kromaattista graafia. Vizingin kirjoituksessa kriittinen kuvaaja, jonka dimensio on k, ymmärretään kuvaajaksi, jonka minkä tahansa ominaisosan mitta on pienempi kuin k. Tässä tapauksessa graafin dimensiolla tarkoitetaan metrisen tilan minimimittausta, johon graafi voidaan upottaa siten, että kaikki vierekkäiset kärjet ovat 1:n etäisyydellä. ( 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 , s. 167.
10. ↑ Hajos, 1961 .
11. ↑ Harari, 2003 , s. 168-169.
12. ↑ Erdős, 1966 .

Kirjallisuus

• R. L. Brooks, W. T. Tutte. Verkon solmujen värittämisestä // Proceedings of the Cambridge Philosophical Society. - 1941. - T. 37 , no. 02 . - S. 194-197 . - doi : 10.1017/S030500410002168X .
• N. G. de Bruijn , P. Erdős . Väriongelma äärettömille kaavioille ja ongelma relaatioteoriassa // Nederl. Akad. Wetensch. Proc. Ser. A. - 1951. - T. 54 . — S. 371–373 . . ( Indag. Matem. 13.)
• GA Dirac. RL Brooksin lause ja H. Hadwigerin arvelu // Proceedings of the London Mathematical Society. - 1957. - T. 7 , no. 1 . - S. 161-195 . - doi : 10.1112/plms/s3-7.1.161 .
• T. Gallai. Kritische Graphen I // Publ. Matematiikka. Inst. unkari. Acad. Sc.. - 1963a. - T. 8 . — S. 165–192 .
• T. Gallai. Kritische Graphen II // Publ. Matematiikka. Inst. unkari. 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 matem.-luonto. Reihe. - 1961. - T. 10 . — S. 116–117 .
• TR Jensen, B. Toft. Graafisten väritysongelmat. - New York: Wiley-Interscience, 1995. - ISBN 0-471-02865-7 .
• Matj Stehlik. Kriittiset kuvaajat yhdistettyjen komplementtien kanssa // Journal of Combinatorial Theory . - 2003. - T. 89 , no. 2 . — S. 189–194 . - doi : 10.1016/S0095-8956(03)00069-8 .
• Laszlo Lovasz . Kombinatoriset ongelmat ja harjoitukset (toinen painos). - Pohjois-Hollanti, 1992.
• Paul Erds . Graafisten teoriassa. — Pros. Colloq., Tihany, 1966. - s. 361.
• V. G. Vising. Joitakin ratkaisemattomia ongelmia graafiteoriassa // Uspekhi Matematicheskikh Nauk. - 1968. - T. XXIII , no. 6 (144) . — s. 117–134 .
• F. Harari. Graafiteoria. - 2. - M. : Pääkirjoitus URSS, 2003. - ISBN 5-354-00301-6 , BBC 22.144, 22.18, 22.19.