| rdfs:comment
| - Le graphe de Grötzsch est, en théorie des graphes, un graphe possédant 11 sommets et 20 arêtes. C'est le plus petit graphe sans triangle de nombre chromatique 4. Il est nommé d'après Herbert Grötzsch qui l'a découvert en 1958. (fr)
- In the mathematical field of graph theory, the Grötzsch graph is a triangle-free graph with 11 vertices, 20 edges, chromatic number 4, and crossing number 5. It is named after German mathematician Herbert Grötzsch, who used it as an example in connection with his 1959 theorem that planar triangle-free graphs are 3-colorable. (en)
- Граф Грёча — граф без треугольников с 11 вершинами, 20 рёбрами, хроматическим числом 4 и числом скрещиваний 5. Граф назван в честь немецкого математика и он демонстрирует необходимость предположения планарности в теореме Грёча (Grötzsch 1959), которая утверждает, что любой планарный граф без треугольников можно раскрасить в 3 цвета. Граф Грёча является членом бесконечной последовательности графов без треугольников, в которой каждый граф является мычельскианом предыдущего графа, начиная с . Эта последовательность графов была использована Мыцельским, чтобы показать, что существуют графы без треугольников с произвольно большим хроматическим числом. По этой причине иногда граф Грёча называют графом Мыцельского или Мыцельского-Грёча. В отличие от других, более поздних графов в последователь (ru)
- Граф Ґрьоча — граф без трикутників з 11 вершинами, 20 ребрами, хроматичним числом 4 і числом схрещень 5. Граф названо на честь німецького математика і він демонструє необхідність припущення планарності в теоремі Ґрьоча (Grötzsch 1959), яка стверджує, що будь-який планарний граф без трикутників можна розфарбувати в 3 кольори. Граф Ґрьоча є членом нескінченної послідовності графів без трикутників, у якій кожен граф є мичельськіаном попереднього графа, починаючи від . Цю послідовність графів використав, щоб показати, що існують графи без трикутників з довільно великим хроматичним числом. З цієї причини іноді граф Ґрьоча називають графом Мичельського або Мичельського — Ґрьоча. На відміну від інших, пізніших графів у послідовності, граф Ґрьоча є найменшим графом без трикутників з його хром (uk)
|
| has abstract
| - In the mathematical field of graph theory, the Grötzsch graph is a triangle-free graph with 11 vertices, 20 edges, chromatic number 4, and crossing number 5. It is named after German mathematician Herbert Grötzsch, who used it as an example in connection with his 1959 theorem that planar triangle-free graphs are 3-colorable. The Grötzsch graph is a member of an infinite sequence of triangle-free graphs, each the Mycielskian of the previous graph in the sequence, starting from the one-edge graph; this sequence of graphs was constructed by to show that there exist triangle-free graphs with arbitrarily large chromatic number. Therefore, the Grötzsch graph is sometimes also called the Mycielski graph or the Mycielski–Grötzsch graph. Unlike later graphs in this sequence, the Grötzsch graph is the smallest triangle-free graph with its chromatic number. (en)
- Le graphe de Grötzsch est, en théorie des graphes, un graphe possédant 11 sommets et 20 arêtes. C'est le plus petit graphe sans triangle de nombre chromatique 4. Il est nommé d'après Herbert Grötzsch qui l'a découvert en 1958. (fr)
- Граф Грёча — граф без треугольников с 11 вершинами, 20 рёбрами, хроматическим числом 4 и числом скрещиваний 5. Граф назван в честь немецкого математика и он демонстрирует необходимость предположения планарности в теореме Грёча (Grötzsch 1959), которая утверждает, что любой планарный граф без треугольников можно раскрасить в 3 цвета. Граф Грёча является членом бесконечной последовательности графов без треугольников, в которой каждый граф является мычельскианом предыдущего графа, начиная с . Эта последовательность графов была использована Мыцельским, чтобы показать, что существуют графы без треугольников с произвольно большим хроматическим числом. По этой причине иногда граф Грёча называют графом Мыцельского или Мыцельского-Грёча. В отличие от других, более поздних графов в последовательности, граф Грёча является наименьшим графом без треугольников с его хроматическим числом. Хеггквист использовал модифицированную версию графа Грёча для опровержения гипотезы Эрдёша и Симоновича о хроматическом числе графов без треугольников, имеющих большую степень. Модификация Хеггквиста заключается в замене каждой из пяти вершин степени четыре графа Грёча тремя вершинами и замене каждой из пяти вершин степени три двумя вершинами. Каждая из оставшихся вершин пятой степени заменяются четырьмя вершинами. Две вершины в этом увеличенном графе соединены ребром, если соответствующие им вершины были соединены ребром в графе Грёча. В результате получаем 10-регулярный граф без треугольников с 29 вершинами и хроматическим числом 4, что опровергает гипотезу, по которой не существует графа без треугольников с хроматическим числом 4 и n вершинами, в котором каждая вершина имеет больше чем n/3 соседей. Граф Грёча имеет хроматический индекс, равный 5, радиус 2, обхват 4 и диаметр 2.Он является также 3-вершинно связным и 3-k-рёберно-связный граф графом. Число независимости графа равно 5 и число доминирования равно 3. (ru)
- Граф Ґрьоча — граф без трикутників з 11 вершинами, 20 ребрами, хроматичним числом 4 і числом схрещень 5. Граф названо на честь німецького математика і він демонструє необхідність припущення планарності в теоремі Ґрьоча (Grötzsch 1959), яка стверджує, що будь-який планарний граф без трикутників можна розфарбувати в 3 кольори. Граф Ґрьоча є членом нескінченної послідовності графів без трикутників, у якій кожен граф є мичельськіаном попереднього графа, починаючи від . Цю послідовність графів використав, щоб показати, що існують графи без трикутників з довільно великим хроматичним числом. З цієї причини іноді граф Ґрьоча називають графом Мичельського або Мичельського — Ґрьоча. На відміну від інших, пізніших графів у послідовності, граф Ґрьоча є найменшим графом без трикутників з його хроматичним числом. Хеггквіст використав модифіковану версію графа Ґрьоча для спростування гіпотези Ердеша і Симоновича про хроматичне число графів без трикутників, що мають великий степінь. Модифікація Хеггквіста полягає в заміні кожної з п'яти вершин степеня чотири графа Ґрьоча трьома вершинами і заміні кожної з п'яти вершин степеня три двома вершинами. Кожна з решти вершин п'ятого степеня замінюються чотирма вершинами. Дві вершини в цьому збільшеному графі з'єднані ребром, якщо відповідні їм вершини були з'єднані ребром у графі Ґрьоча. В результаті отримуємо 10-регулярний граф без трикутників з 29 вершинами і хроматичним числом 4, що спростовує гіпотезу, за якою не існує графа без трикутників з хроматичним числом 4 і n вершинами, у якому кожна вершина має більше ніж n/3 сусідів. Граф Ґрьоча має хроматичний Індекс, рівний 5, радіус 2, обхват 4 і діаметр 2. Він є також 3-вершинно зв'язним і 3-k-реберно-зв'язним графом. Число незалежності графа дорівнює 5 і число домінування дорівнює 3. (uk)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
