Brinkmann graph

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

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]

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^21 - 42x^20 + 861x^19 - 11480x^18 + 111881x^17 - 848708x^16 + 5207711x^15 - 26500254x^14 + 113675219x^13 - 415278052x^12 + 1299042255x^11 - 3483798283x^10 + 7987607279x^9 - 15547364853x^8 + 25384350310x^7 - 34133692383x^6 + 36783818141x^5 - 30480167403x^4 + 18168142566x^3 - 6896700738x^2 + 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.

References

1. Brinkmann, G. "Generating Cubic Graphs Faster Than Isomorphism Checking." Preprint 92-047 SFB 343. Bielefeld, Germany: University of Bielefeld, 1992.
2. Brinkmann, G. and Meringer, M. "The Smallest 4-Regular 4-Chromatic Graphs with Girth 5." Graph Theory Notes of New York 32, 40-41, 1997.
3. Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
4. Erdős, Paul (1959), "Graph theory and probability", Canadian Journal of Mathematics, 11: 34–38, doi:10.4153/CJM-1959-003-9.
5. Grünbaum, B. (1970), "A problem in graph coloring", American Mathematical Monthly, 77 (10), Mathematical Association of America: 1088–1092, doi:10.2307/2316101, JSTOR 2316101.
6. Reed, B. A. (1998), "ω, Δ, and χ", Journal of Graph Theory, 27 (4): 177–212, doi:10.1002/(SICI)1097-0118(199804)27:4<177::AID-JGT1>3.0.CO;2-K.

External links

• Weisstein, Eric W. "Brinkmann graph". MathWorld.