Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Brinkmann_graph> ?p ?o }
Showing triples 1 to 59 of
59
with 100 triples per page.
- Brinkmann_graph 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.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 A159192 in OEIS).".
- Brinkmann_graph thumbnail Brinkmann_graph_LS.svg?width=300.
- Brinkmann_graph wikiPageID "24177385".
- Brinkmann_graph wikiPageLength "4615".
- Brinkmann_graph wikiPageOutDegree "24".
- Brinkmann_graph wikiPageRevisionID "699509613".
- Brinkmann_graph wikiPageWikiLink Big_O_notation.
- Brinkmann_graph wikiPageWikiLink Brooks_theorem.
- Brinkmann_graph wikiPageWikiLink Category:4-chromatic_graphs.
- Brinkmann_graph wikiPageWikiLink Category:Individual_graphs.
- Brinkmann_graph wikiPageWikiLink Category:Regular_graphs.
- Brinkmann_graph wikiPageWikiLink Characteristic_polynomial.
- Brinkmann_graph wikiPageWikiLink Chromatic_polynomial.
- Brinkmann_graph wikiPageWikiLink Chvátal_graph.
- Brinkmann_graph wikiPageWikiLink Dihedral_group.
- Brinkmann_graph wikiPageWikiLink Edge_coloring.
- Brinkmann_graph wikiPageWikiLink Eulerian_path.
- Brinkmann_graph wikiPageWikiLink Graph_coloring.
- Brinkmann_graph wikiPageWikiLink Graph_theory.
- Brinkmann_graph wikiPageWikiLink Hamiltonian_path.
- Brinkmann_graph wikiPageWikiLink Heptagon.
- Brinkmann_graph wikiPageWikiLink K-edge-connected_graph.
- Brinkmann_graph wikiPageWikiLink K-vertex-connected_graph.
- Brinkmann_graph wikiPageWikiLink Mathematics.
- Brinkmann_graph wikiPageWikiLink Regular_graph.
- Brinkmann_graph wikiPageWikiLink Vertex-transitive_graph.
- Brinkmann_graph wikiPageWikiLink File:Brinkmann_graph_LS.svg.
- Brinkmann_graph wikiPageWikiLinkText "Brinkmann graph".
- Brinkmann_graph automorphisms "14".
- Brinkmann_graph chromaticIndex "5".
- Brinkmann_graph chromaticNumber "4".
- Brinkmann_graph diameter "3".
- Brinkmann_graph edges "42".
- Brinkmann_graph girth "5".
- Brinkmann_graph imageCaption "The Brinkmann graph".
- Brinkmann_graph name "Brinkmann graph".
- Brinkmann_graph namesake "Gunnar Brinkmann".
- Brinkmann_graph properties Eulerian_path.
- Brinkmann_graph properties Hamiltonian_path.
- Brinkmann_graph radius "3".
- Brinkmann_graph vertices "21".
- Brinkmann_graph wikiPageUsesTemplate Template:Infobox_graph.
- Brinkmann_graph wikiPageUsesTemplate Template:OEIS.
- Brinkmann_graph wikiPageUsesTemplate Template:Reflist.
- Brinkmann_graph subject Category:4-chromatic_graphs.
- Brinkmann_graph subject Category:Individual_graphs.
- Brinkmann_graph subject Category:Regular_graphs.
- Brinkmann_graph hypernym Graph.
- Brinkmann_graph type Software.
- Brinkmann_graph type Graph.
- Brinkmann_graph comment "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.".
- Brinkmann_graph label "Brinkmann graph".
- Brinkmann_graph sameAs Q3115474.
- Brinkmann_graph sameAs Graphe_de_Brinkmann.
- Brinkmann_graph sameAs m.07kjpkw.
- Brinkmann_graph sameAs Q3115474.
- Brinkmann_graph wasDerivedFrom Brinkmann_graph?oldid=699509613.
- Brinkmann_graph depiction Brinkmann_graph_LS.svg.
- Brinkmann_graph isPrimaryTopicOf Brinkmann_graph.