| dbo:abstract
|
- In the mathematical field of graph theory, the Brinkmann graph is a 4-regular graph with 21 vertices and 42 edges discovered by Gunnar Brinkmann in 1992. It was first published by Brinkmann and Meringer in 1997. It has chromatic number 4, chromatic index 5, radius 3, diameter 3 and girth 5. It is also a 3-vertex-connected graph and a 3-edge-connected graph. It is the smallest 4-regular graph of girth 5 with chromatic number 4. It has book thickness 3 and queue number 2. By Brooks’ theorem, every k-regular graph (except for odd cycles and cliques) has chromatic number at most k. It was also known since 1959 that, for every k and l there exist k-chromatic graphs with girth l. In connection with these two results and several examples including the Chvátal graph, Branko Grünbaum conjectured in 1970 that for every k and l there exist k-chromatic k-regular graphs with girth l. The Chvátal graph solves the case k = l = 4 of this conjecture and the Brinkmann graph solves the case k = 4, l = 5. Grünbaum's conjecture was disproved for sufficiently large k by Johannsen, who showed that the chromatic number of a triangle-free graph is O(Δ/log Δ) where Δ is the maximum vertex degree and the O introduces big O notation. However, despite this disproof, it remains of interest to find examples and only very few are known. The chromatic polynomial of the Brinkmann graph is x21 - 42x20 + 861x19 - 11480x18 + 111881x17 - 848708x16 + 5207711x15 - 26500254x14 + 113675219x13 - 415278052x12 + 1299042255x11 - 3483798283x10 + 7987607279x9 - 15547364853x8 + 25384350310x7 - 34133692383x6 + 36783818141x5 - 30480167403x4 + 18168142566x3 - 6896700738x2 + 1242405972x (sequence in the OEIS). (en)
- Le graphe de Brinkmann est, en théorie des graphes, un graphe 4-régulier possédant 21 sommets et 42 arêtes. (fr)
- Граф Бринкмана — 4-регулярный граф с 21 вершинами и 42 рёбрами, обнаруженный Гуннаром Бринкманом в 1992 году. Опубликовали его Бринкман и Мерингер в 1997 году. Граф имеет хроматическое число 4, хроматический индекс 5, радиус 3, диаметр 3 и обхват 5. Он также вершинно 3-связен и рёберно 3-связен. Это самый маленький 4-регулярный граф обхвата 5 с хроматическим числом 4. Граф имеет книжную толщину 3 и число очередей 2. (ru)
|
| dbo:thumbnail
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 4749 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:automorphisms
| |
| dbp:bookThickness
| |
| dbp:chromaticIndex
| |
| dbp:chromaticNumber
| |
| dbp:diameter
| |
| dbp:edges
| |
| dbp:girth
| |
| dbp:imageCaption
| |
| dbp:name
| |
| dbp:namesake
| |
| dbp:properties
| |
| dbp:queueNumber
| |
| dbp:radius
| |
| dbp:vertices
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- Le graphe de Brinkmann est, en théorie des graphes, un graphe 4-régulier possédant 21 sommets et 42 arêtes. (fr)
- Граф Бринкмана — 4-регулярный граф с 21 вершинами и 42 рёбрами, обнаруженный Гуннаром Бринкманом в 1992 году. Опубликовали его Бринкман и Мерингер в 1997 году. Граф имеет хроматическое число 4, хроматический индекс 5, радиус 3, диаметр 3 и обхват 5. Он также вершинно 3-связен и рёберно 3-связен. Это самый маленький 4-регулярный граф обхвата 5 с хроматическим числом 4. Граф имеет книжную толщину 3 и число очередей 2. (ru)
- In the mathematical field of graph theory, the Brinkmann graph is a 4-regular graph with 21 vertices and 42 edges discovered by Gunnar Brinkmann in 1992. It was first published by Brinkmann and Meringer in 1997. It has chromatic number 4, chromatic index 5, radius 3, diameter 3 and girth 5. It is also a 3-vertex-connected graph and a 3-edge-connected graph. It is the smallest 4-regular graph of girth 5 with chromatic number 4. It has book thickness 3 and queue number 2. (en)
|
| rdfs:label
|
- Brinkmann graph (en)
- Graphe de Brinkmann (fr)
- Граф Бринкмана (ru)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
