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

• Faktorkritisk graf

Anteckningar

1. ↑ 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 )
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 , sid. 167.
10. ↑ Hajos, 1961 .
11. ↑ Harari, 2003 , sid. 168-169.
12. ↑ 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.