Grötzsch graf
| Grötzsch graf | |
|---|---|
 | |
| Döpt efter | Herbert Grötzsch |
| Vertices | 11 |
| Kanter | 20 |
| Radie | 2 |
| Diameter | 2 |
| Omkrets | 4 |
| Automorfismer | 10 ( D 5 ) |
| Kromatiskt nummer | 4 |
| Kromatiskt index | 5 |
| Boktjocklek | 3 |
| Könummer | 2 |
| Egenskaper | |
| Tabell över grafer och parametrar | |
Inom det matematiska området grafteorin är Grötzsch-grafen en triangelfri graf med 11 hörn, 20 kanter, kromatiskt nummer 4, och korsningsnummer 5. Den är uppkallad efter den tyske matematikern Herbert Grötzsch , som använde den som exempel i samband med med hans sats från 1959 att plana triangelfria grafer är 3-färgbara.
Grötzsch-grafen är en medlem av en oändlig sekvens av triangelfria grafer, var och en Mycielskian av föregående graf i sekvensen, med början från enkantsgrafen; denna sekvens av grafer konstruerades av Mycielski (1955) för att visa att det finns triangelfria grafer med godtyckligt stora kromatiska tal. Därför kallas Grötzsch-grafen ibland också Mycielski-grafen eller Mycielski–Grötzsch-grafen. Till skillnad från senare grafer i denna sekvens är Grötzsch-grafen den minsta triangelfria grafen med sitt kromatiska tal.
Egenskaper
Den fullständiga automorfismgruppen i Grötzsch-grafen är isomorf till den dihedriska gruppen D 5 av ordning 10, gruppen av symmetrier för en regelbunden femhörning , inklusive både rotationer och reflektioner. Dessa symmetrier har tre omloppsbanor av hörn: grad-5 vertex (av sig själv), dess fem grannar och dess fem icke-grannar. På samma sätt finns det tre kanterbanor, kännetecknade av deras avstånd från grader-5 vertex.
Det karakteristiska polynomet för Grötzsch-grafen är
Även om det inte är en plan graf , kan den bäddas in i det projektiva planet utan korsningar. Denna inbäddning har tio ytor, som alla är fyrhörningar.
Ansökningar
Förekomsten av Grötzsch-grafen visar att antagandet om planaritet är nödvändigt i Grötzschs teorem att varje triangelfri plan graf är 3-färgbar. Den har udda omkrets fem men omkrets fyra och har ingen grafhomomorfism till en graf vars omkrets är fem eller mer, så den utgör ett exempel som skiljer udda omkrets från den maximala omkrets som kan erhållas från en homomorfism.
Häggkvist (1981) använde en modifierad version av Grötzsch-grafen för att motbevisa en gissning av Paul Erdős och Miklos Simonovits ( 1973 ) om det kromatiska antalet triangelfria grafer med hög grad. Häggkvists modifiering består i att ersätta var och en av de fem grader-fyra hörnen i Grötzsch-grafen med en uppsättning av tre hörn, att ersätta var och en av de fem grader-tre hörnen i Grötzsch-grafen med en uppsättning av två hörn, och ersätta den återstående grad- fem hörn av Grötzsch-grafen med en uppsättning av fyra hörn. Två hörn i denna utökade graf är sammankopplade med en kant om de motsvarar hörn sammankopplade med en kant i Grötzsch-grafen. Resultatet av Häggkvists konstruktion är en 10- reguljär triangelfri graf med 29 hörn och kromatiskt nummer 4, vilket motbevisar gissningen att det inte finns någon 4-kromatisk triangelfri n {\ -vertexgraf där varje vertex har mer än grannar. Varje sådan graf innehåller Grötzsch-grafen som en inducerad subgraf .
Relaterade grafer
Grötzsch-grafen delar flera egenskaper med Clebsch-grafen , en avståndstransitiv graf med 16 hörn och 40 kanter: både Grötzsch-grafen och Clebsch-grafen är triangelfria och fyrkromatiska, och ingen av dem har någon sex- vertexinducerad stigar . Dessa egenskaper är nära att vara tillräckliga för att karakterisera dessa grafer: Grötzsch-grafen är en inducerad subgraf av Clebsch-grafen, och varje triangelfri fyrkromatisk -fri graf är likaså en inducerad subgraf av Clebsch-grafen som i sin tur innehåller Grötzsch-grafen som en inducerad subgraf. Chvátal -grafen är en annan liten triangelfri 4-kromatisk graf. Men till skillnad från Grötzsch-grafen och Clebsch-grafen har Chvátal-grafen en sex-vertex-inducerad bana.
Anteckningar
- Brandt, Stephan (1999), "Om strukturen av täta triangelfria grafer", Combinatorics, Probability and Computing , 8 (3): 237–245, doi : 10.1017/S0963548399003831 , MR 1702550
- Chvátal, Vašek (1974), "The minimality of the Mycielski graph", Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, DC, 1973) , Berlin: Lecture Notes in Mathematics, Vol. 406, Springer-Verlag, s. 243–246, MR 0360330
- Erdős, P. ; Simonovits, M. (1973), "On a valence problem in extremal graph theory", Discrete Mathematics , 5 (4): 323–334, doi : 10.1016/0012-365X(73)90126-X , MR 0342429
- Galluccio, Anna; Goddyn, Luis A.; Hell, Pavol (2001), "High-girth graphs avoiding a minor are nearly bipartite", Journal of Combinatorial Theory , Series B, 83 (1): 1–14, doi : 10.1006/jctb.2000.2009 , MR 1855739
- Grötzsch, Herbert (1959), "Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel", Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe , 8 : 109–120, MR 0116320
- Häggkvist, R. (1981), "Od cycles of specific length in nonbipartite graphs", Graph Theory (Cambridge, 1981) , s. 89–99, MR 0671908
- Joyner, W. David; Melles, Caroline Grant (2017), "5.12 Grötzsch graph", Adventures in Graph Theory , Applied and Numerical Harmonic Analysis, Birkhäuser/Springer, Cham, s. 229–231, doi : 10.1007/978-3-3819-683 , ISBN 978-3-319-68381-2 , MR 3753658
- Mycielski, Jan (1955), "Sur le coloriage des graphs", Colloq. Matematik. , 3 (2): 161–162, doi : 10.4064/cm-3-2-161-162 , MR 0069494
- Randerath, Bert; Schiermeyer, Ingo; Tewes, Meike (2002), "Three-colourability and forbidden subgraphs. II. Polynomial algorithms", Discrete Mathematics , 251 (1–3): 137–153, doi : 10.1016/S0012-365X(01 ) 00335-1 1904597
- Youngs, DA (1996), "4-chromatic projective graphs", Journal of Graph Theory , 21 (2): 219–227, doi : 10.1002/(SICI)1097-0118(199602)21:2<219::AID -JGT12>3.0.CO;2-E , MR 1368748