Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Граф Ґрьоча граф без трикутників з 11 вершинами 20 ребрами хроматичним числом 4 і числом схрещень 5 Граф названо на чест

Граф Ґрьоча

Граф Ґрьоча

Граф Ґрьоча — граф без трикутників з 11 вершинами, 20 ребрами, хроматичним числом 4 і числом схрещень 5. Граф названо на честь німецького математика [en] і він демонструє необхідність припущення планарності в теоремі Ґрьоча (Grötzsch 1959), яка стверджує, що будь-який планарний граф без трикутників можна розфарбувати в 3 кольори. Граф Ґрьоча є членом нескінченної послідовності графів без трикутників, у якій кожен граф є мичельськіаном попереднього графа, починаючи від [en]. Цю послідовність графів використав [ru] (Mycielski, 1955), щоб показати, що існують графи без трикутників з довільно великим хроматичним числом. З цієї причини іноді граф Ґрьоча називають графом Мичельського або Мичельського — Ґрьоча. На відміну від інших, пізніших графів у послідовності, граф Ґрьоча є найменшим графом без трикутників з його хроматичним числом (Chvátal, 1974).

image

Хеггквіст (Häggkvist, 1981) використав модифіковану версію графа Ґрьоча для спростування гіпотези Ердеша і Симоновича (Erdős, Simonovits, 1973) про хроматичне число графів без трикутників, що мають великий степінь. Модифікація Хеггквіста полягає в заміні кожної з п'яти вершин степеня чотири графа Ґрьоча трьома вершинами і заміні кожної з п'яти вершин степеня три двома вершинами. Кожна з решти вершин п'ятого степеня замінюються чотирма вершинами. Дві вершини в цьому збільшеному графі з'єднані ребром, якщо відповідні їм вершини були з'єднані ребром у графі Ґрьоча. В результаті отримуємо 10-регулярний граф без трикутників з 29 вершинами і хроматичним числом 4, що спростовує гіпотезу, за якою не існує графа без трикутників з хроматичним числом 4 і n вершинами, у якому кожна вершина має більше ніж n/3 сусідів.

Граф Ґрьоча має хроматичний Індекс, рівний 5, радіус 2, обхват 4 і діаметр 2. Він є також 3-вершинно зв'язним і 3-k-реберно-зв'язним графом. Число незалежності графа дорівнює 5 і число домінування дорівнює 3.

Алгебричні властивості

Повна група автоморфізмів графа Ґрьоча ізоморфна діедральній групі D5 десятого порядку, групі симетрій правильного п'ятикутника, що включає обертання і відбиття.

Характеристичним многочленом графа Ґрьоча є

image

Див. також

  • Граф Хватала — ще один маленький граф без трикутників, розфарбовуваний у 4 кольори.

Література

  • Chvátal. Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973). — Berlin : Lecture Notes in Mathematics, Vol. 406, Springer-Verlag, 1974. — С. 243–246. — MR0360330..
  • On a valence problem in extremal graph theory // . — 1973. — Т. 5, вип. 4. — С. 323–334. — DOI:10.1016/0012-365X(73)90126-X. — MR0342429..
  • Grötzsch. 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. — 1959. — Т. 8. — С. 109–120. — MR0116320..
  • Häggkvist. Odd cycles of specified length in nonbipartite graphs. — 1981. — С. 89–99. — MR0671908..
  • . Sur le coloriage des graphs // Colloq. Math.. — 1955. — Т. 3. — С. 161–162. — MR0069494..

Посилання

  • Weisstein, Eric W. Граф Ґрьоча(англ.) на сайті Wolfram MathWorld.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Graf Grocha graf bez trikutnikiv z 11 vershinami 20 rebrami hromatichnim chislom 4 i chislom shreshen 5 Graf nazvano na chest nimeckogo matematika en i vin demonstruye neobhidnist pripushennya planarnosti v teoremi Grocha Grotzsch 1959 yaka stverdzhuye sho bud yakij planarnij graf bez trikutnikiv mozhna rozfarbuvati v 3 kolori Graf Grocha ye chlenom neskinchennoyi poslidovnosti grafiv bez trikutnikiv u yakij kozhen graf ye michelskianom poperednogo grafa pochinayuchi vid en Cyu poslidovnist grafiv vikoristav ru Mycielski 1955 shob pokazati sho isnuyut grafi bez trikutnikiv z dovilno velikim hromatichnim chislom Z ciyeyi prichini inodi graf Grocha nazivayut grafom Michelskogo abo Michelskogo Grocha Na vidminu vid inshih piznishih grafiv u poslidovnosti graf Grocha ye najmenshim grafom bez trikutnikiv z jogo hromatichnim chislom Chvatal 1974 Heggkvist Haggkvist 1981 vikoristav modifikovanu versiyu grafa Grocha dlya sprostuvannya gipotezi Erdesha i Simonovicha Erdos Simonovits 1973 pro hromatichne chislo grafiv bez trikutnikiv sho mayut velikij stepin Modifikaciya Heggkvista polyagaye v zamini kozhnoyi z p yati vershin stepenya chotiri grafa Grocha troma vershinami i zamini kozhnoyi z p yati vershin stepenya tri dvoma vershinami Kozhna z reshti vershin p yatogo stepenya zaminyuyutsya chotirma vershinami Dvi vershini v comu zbilshenomu grafi z yednani rebrom yaksho vidpovidni yim vershini buli z yednani rebrom u grafi Grocha V rezultati otrimuyemo 10 regulyarnij graf bez trikutnikiv z 29 vershinami i hromatichnim chislom 4 sho sprostovuye gipotezu za yakoyu ne isnuye grafa bez trikutnikiv z hromatichnim chislom 4 i n vershinami u yakomu kozhna vershina maye bilshe nizh n 3 susidiv Graf Grocha maye hromatichnij Indeks rivnij 5 radius 2 obhvat 4 i diametr 2 Vin ye takozh 3 vershinno zv yaznim i 3 k reberno zv yaznim grafom Chislo nezalezhnosti grafa dorivnyuye 5 i chislo dominuvannya dorivnyuye 3 Algebrichni vlastivostiPovna grupa avtomorfizmiv grafa Grocha izomorfna diedralnij grupi D5 desyatogo poryadku grupi simetrij pravilnogo p yatikutnika sho vklyuchaye obertannya i vidbittya Harakteristichnim mnogochlenom grafa Grocha ye x 1 5 x 2 x 10 x 2 3 x 1 2 displaystyle x 1 5 x 2 x 10 x 2 3x 1 2 Div takozhGraf Hvatala she odin malenkij graf bez trikutnikiv rozfarbovuvanij u 4 kolori LiteraturaChvatal Graphs and combinatorics Proc Capital Conf George Washington Univ Washington D C 1973 Berlin Lecture Notes in Mathematics Vol 406 Springer Verlag 1974 S 243 246 MR0360330 On a valence problem in extremal graph theory 1973 T 5 vip 4 S 323 334 DOI 10 1016 0012 365X 73 90126 X MR0342429 Grotzsch Zur Theorie der diskreten Gebilde VII Ein Dreifarbensatz fur dreikreisfreie Netze auf der Kugel Wiss Z Martin Luther U Halle Wittenberg Math Nat Reihe 1959 T 8 S 109 120 MR0116320 Haggkvist Odd cycles of specified length in nonbipartite graphs 1981 S 89 99 MR0671908 Sur le coloriage des graphs Colloq Math 1955 T 3 S 161 162 MR0069494 PosilannyaWeisstein Eric W Graf Grocha angl na sajti Wolfram MathWorld

Дата публікації:
Топ