The Brinkmann graph (misspelled by Cancela et al. (2004) as "Brinkman") is a weakly regularquartic
graph on 21 vertices and 42 edges. It was first mentioned in Brinkmann (1992)
and first published as a note in Brinkmann and Meringer (1997). It is implemented
in the Wolfram Language as GraphData["BrinkmannGraph"].
Grünbaum conjectured that for every integer , , there exists an -regular, -chromatic graph of girth at least
. This result is trivial for and , but only a small number of other such graphs are known,
including the Brinkmann graph, illustrated above, Chvátal
graph, and 25-Grünbaum graph.
Bollobás, B. Modern Graph Theory. New York: Springer-Verlag, 1998.Brinkmann, G.
"Generating Cubic Graphs Faster Than Isomorphism Checking." Preprint 92-047
SFB 343. Bielefeld, Germany: University of Bielefeld, 1992.Brinkmann,
G. and Meringer, M. "The Smallest 4-Regular 4-Chromatic Graphs with Girth 5."
Graph Theory Notes of New York32, 40-41, 1997.Cancela,
H.; Robledo, F.; and Rubino, G. "A GRASP Algorithm with Tree Based Local Search
for Designing a Survivable Wide Area Network Backbone." J. Computer Sci.
Technol.4, 52-58, 2004. http://journal.info.unlp.edu.ar/journal/journal10/papers/JCST-Apr04-8.pdf.Grünbaum,
B. "A Problem in Graph Coloring." Amer. Math. Monthly77,
1088-1092, 1970.
, 
, there exists an 
-regular, 
-chromatic graph of girth at least
. This result is trivial for 
and 
, but only a small number of other such graphs are known,
including the Brinkmann graph, illustrated above, Chvátal
graph, and 25-Grünbaum graph.
