Brinkmann graph

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.^[1] It was first published by Brinkmann and Meringer in 1997.^[2]

Brinkmann graph
The Brinkmann graph
Named after	Gunnar Brinkmann
Vertices	21
Edges	42
Radius	3
Diameter	3
Girth	5
Automorphisms	14 (D7)
Chromatic number	4
Chromatic index	5
Book thickness	3
Queue number	2
Properties	Eulerian Hamiltonian
Table of graphs and parameters

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.^[2] It has book thickness 3 and queue number 2.^[3]

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.^[4] 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.^[5] 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.^[6] 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 x²¹ − 42x²⁰ + 861x¹⁹ − 11480x¹⁸ + 111881x¹⁷ − 848708x¹⁶ + 5207711x¹⁵ − 26500254x¹⁴ + 113675219x¹³ − 415278052x¹² + 1299042255x¹¹ − 3483798283x¹⁰ + 7987607279x⁹ − 15547364853x⁸ + 25384350310x⁷ − 34133692383x⁶ + 36783818141x⁵ − 30480167403x⁴ + 18168142566x³ − 6896700738x² + 1242405972x (sequence A159192 in the OEIS).

Algebraic properties

The Brinkmann graph is not a vertex-transitive graph and its full automorphism group is isomorphic to the dihedral group of order 14, the group of symmetries of a heptagon, including both rotations and reflections.

The characteristic polynomial of the Brinkmann graph is ${\displaystyle (x-4)(x-2)(x+2)(x^{3}-x^{2}-2x+1)^{2}}$${\displaystyle (x^{6}+3x^{5}-8x^{4}-21x^{3}+27x^{2}+38x-41)^{2}}$.

Gallery

• 
  Alternative drawing of Brinkmann Graph.
• 
  The chromatic number of the Brinkmann graph is 4.
• 
  The chromatic index of the Brinkmann graph is 5.