Kritisk graf
En kritisk graf är en graf där borttagningen av någon vertex eller kant minskar grafens kromatiska tal .
Relaterade definitioner
- -kritisk graf är en kritisk graf med kromatiskt tal k .
- En graf G med kromatiskt tal k är vertex - k - kritisk om var och en av dess hörn är ett kritiskt element [1] .
Egenskaper
- Låt G vara en k -kritisk graf med n hörn och m kanter. Sedan:
- G har bara en komponent .
- G är finit ( de Bruijn-Erdős sats [2] ).
- δ( G ) ≥ k − 1, det vill säga vilken vertex som helst ligger intill åtminstone k − 1 andra hörn. Mer strikt är G ( k − 1)-kantansluten [3] .
- Om grafen G är ( k − 1)-regelbunden (varje vertex ligger intill exakt k − 1 andra), så är grafen G antingen en komplett graf K k eller en udda cykel . (Detta är Brooks teorem [4] ).
- 2 m ≥ ( k − 1) n + k − 3 [5] .
- 2 m ≥ ( k − 1) n + [( k − 3)/( k 2 − 3)] n [6] .
- Antingen kan G delas upp i två mindre kritiska grafer med en kant mellan varje par av hörn, där två hörn kommer från olika delar, eller så har G minst 2k - 1 hörn [7] . Mer strikt, antingen har G nedbrytningar av denna typ, eller för varje vertex v i grafen G finns det en k -färgning där v är den enda vertexen med sin egen färg, och alla andra färgklasser har minst två hörn [8 ] .
- En graf G är vertexkritisk om och endast om det för någon vertex v finns en optimal lämplig färgning där spetsen v ensam representerar färgklassen.
- 1-kritiska grafer finns inte.
- Den enda 2-kritiska grafen är K 2 .
- Alla 3-kritiska grafer är uttömda av enkla cykler med udda längd [9] .
- Som Hajos [10] visade kan vilken k -kritisk graf som helst bildas från en komplett graf K k genom att kombinera konstruktionen av Hajos med operationen att identifiera två icke-angränsande hörn. Grafen som bildas på detta sätt kräver alltid k färger i valfri färg.
- Även om varje linjekritisk graf nödvändigtvis är kritisk, är det omvända inte sant. Till exempel är grafen till höger 4-kritisk men inte kantkritisk [11] .
Variationer och generaliseringar
- En dubbelkritisk graf är en sammankopplad graf där borttagandet av valfritt par av angränsande hörn reducerar det kromatiska talet med två. Ett av de olösta problemen är om K k är den enda dubbelkritiska k - kromatiska grafen [12] .
Se även
Anteckningar
- ↑ Det bör noteras att en kritisk graf inte alltid förstås som en kritisk k -kromatisk graf. I Vizings uppsats förstås en kritisk graf av dimensionen k som en graf vars dimension av någon egendel är mindre än k. I det här fallet förstås dimensionen av en graf som den minsta dimensionen av ett metriskt utrymme i vilket grafen kan bäddas in så att alla intilliggande hörn är på avståndet 1. ( Vizing 1968 )
- ↑ de Bruijn, Erdős, 1951 .
- ↑ Lovász, 1992 .
- ↑ Brooks, Tutte, 1941 .
- ↑ Dirac, 1957 .
- ↑ Gallai, 1963a .
- ↑ Gallai, 1963b .
- ↑ Stehlik, 2003 .
- ↑ Harari, 2003 , sid. 167.
- ↑ Hajos, 1961 .
- ↑ Harari, 2003 , sid. 168-169.
- ↑ Erdős, 1966 .
Litteratur
- R.L. Brooks, W.T. Tutte. Om färgläggning av noderna i ett nätverk // Proceedings of the Cambridge Philosophical Society. - 1941. - T. 37 , nr. 02 . — S. 194–197 . - doi : 10.1017/S030500410002168X .
- N. G. de Bruijn , P. Erdős . Ett färgproblem för oändliga grafer och ett problem i relationsteorin // Nederl. Akad. Wetensch. Proc. Ser. A. - 1951. - T. 54 . — S. 371–373 . . ( Indag. Math. 13.)
- GA Dirac. Ett teorem av RL Brooks och en gissning av H. Hadwiger // Proceedings of the London Mathematical Society. - 1957. - T. 7 , nr. 1 . — S. 161–195 . - doi : 10.1112/plms/s3-7.1.161 .
- T. Gallai. Kritische Graphen I // Publ. Matematik. Inst. hungar. Acad. Sc.. - 1963a. - T. 8 . — S. 165–192 .
- T. Gallai. Kritische Graphen II // Publ. Matematik. Inst. hungar. 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. Graffärgningsproblem. - New York: Wiley-Interscience, 1995. - ISBN 0-471-02865-7 .
- Matj Stehlik. Kritiska grafer med anslutna komplement // Journal of Combinatorial Theory . - 2003. - T. 89 , nr. 2 . — S. 189–194 . - doi : 10.1016/S0095-8956(03)00069-8 .
- Laszlo Lovasz . Kombinatoriska problem och övningar (andra upplagan). — Nord-Holland, 1992.
- Paul Erds . I Theory of Graphs. — Proc. Colloq., Tihany, 1966. - S. 361.
- V. G. Vizing. Några olösta problem i grafteori // Uspekhi Matematheskikh Nauk. - 1968. - T. XXIII , nr. 6 (144) . — s. 117–134 .
- F. Harari. Grafteori. - 2:a. - M. : Editorial URSS, 2003. - ISBN 5-354-00301-6 , BBC 22.144, 22.18, 22.19.