Gráfico de Brinkmann

En el campo matemático de la teoría de grafos , el grafo de Brinkmann es un grafo 4-regular con 21 vértices y 42 aristas descubierto por Gunnar Brinkmann en 1992. ^{[ 1 ]} Fue publicado por primera vez por Brinkmann y Meringer en 1997. ^{[ 2 ]}

Tiene número cromático 4, índice cromático 5, radio 3, diámetro 3 y circunferencia 5. También es un grafo 3-conexo por vértices y un grafo 3-conexo por aristas . Es el grafo 4-regular más pequeño de circunferencia 5 con número cromático 4. ^{[ 2 ]} Tiene grosor de libro 3 y número de cola 2. ^{[ 3 ]} El grafo no es 1-planar . ^{[ 4 ]}

Según el teorema de Brooks , todo grafo k -regular (excepto ciclos impares y camarillas) tiene un número cromático como máximo k . También se sabía desde 1959 que, para cada k y l existen grafos k -cromáticos con circunferencia l . ^{[ 5 ]} En relación con estos dos resultados y varios ejemplos, incluido el grafo de Chvátal , Branko Grünbaum conjeturó en 1970 que para cada k y l existen grafos k -regulares k - cromáticos con circunferencia l . ^{[ 6 ]} El grafo de Chvátal resuelve el caso k  = l = 4 de esta conjetura y el grafo de Brinkmann resuelve el caso k = 4, l = 5. La conjetura de Grünbaum fue refutada para k suficientemente grande por Johannsen, quien demostró que el número cromático de un grafo sin triángulos es O(Δ/log Δ) donde Δ es el grado máximo del vértice y la O introduce la notación de la gran O. ^{[ 7 ]} Sin embargo, a pesar de esta refutación, sigue siendo interesante encontrar ejemplos y solo se conocen muy pocos.        

El polinomio cromático del gráfico de Brinkmann es x ²¹ − 42 x ²⁰ + 861 x ¹⁹ − 11480 x ¹⁸ + 111881 x ¹⁷ − 848708 x ¹⁶ + 5207711 x ¹⁵ − 26500254 x ¹⁴ + 113675219 x ¹³ − 415278052 x ¹² + 1299042255 x ¹¹ − 3483798283 x ¹⁰ + 7987607279 x ⁹ − 15547364853 x ⁸ + 25384350310 x ⁷ − 34133692383 x ⁶ + 36783818141 x ⁵ − 30480167403 x ⁴ + 18168142566 x ³ − 6896700738 x ² + 1242405972 x (secuencia A159192 en el OEIS ) .

El grafo de Brinkmann no es un grafo transitivo de vértices y su grupo de automorfismos completo es isomorfo al grupo diedral de orden 14, el grupo de simetrías de un heptágono , que incluye tanto rotaciones como reflexiones.

El polinomio característico del grafo de Brinkmann es${\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}}$.

• 
  Representación gráfica alternativa de Brinkmann.
• 
  El número cromático del gráfico de Brinkmann es 4.
• 
  El índice cromático del gráfico de Brinkmann es 5.

• Weisstein, Eric W. "Gráfico de Brinkmann" . MundoMatemático .