En el campo matemático de la teoría de grafos , la gráfica de Tietze es una gráfica cúbica no dirigida con 12 vértices y 18 aristas. Lleva el nombre de Heinrich Franz Friedrich Tietze , quien demostró en 1910 que la franja de Möbius se puede subdividir en seis regiones que se tocan entre sí (tres a lo largo del límite de la franja y tres a lo largo de su línea central) y, por lo tanto, los gráficos que están incrustados sobre la tira de Möbius pueden ser necesarios seis colores . [1] Los segmentos límite de las regiones de la subdivisión de Tietze (incluidos los segmentos a lo largo del límite de la propia franja de Möbius) forman una incrustación del gráfico de Tietze.
El gráfico de Tietze se puede formar a partir del gráfico de Petersen reemplazando uno de sus vértices por un triángulo . [2] [3] Al igual que el gráfico de Tietze, el gráfico de Petersen forma el límite de seis regiones que se tocan entre sí, pero en el plano proyectivo en lugar de en la franja de Möbius. Si se corta un agujero de esta subdivisión del plano proyectivo, rodeando un solo vértice, el vértice rodeado se reemplaza por un triángulo de límites de región alrededor del agujero, dando la construcción descrita anteriormente del gráfico de Tietze.
Tanto el gráfico de Tietze como el de Petersen son máximamente no hamiltonianos : no tienen ciclo hamiltoniano , pero dos vértices cualesquiera no adyacentes pueden conectarse mediante un camino hamiltoniano. [2] El gráfico de Tietze y el gráfico de Petersen son los únicos gráficos cúbicos no hamiltonianos conectados con 2 vértices y con 12 vértices o menos. [4]
A diferencia del gráfico de Petersen, el gráfico de Tietze no es hipohamiltoniano : al eliminar uno de los tres vértices del triángulo se forma un gráfico más pequeño que sigue siendo no hamiltoniano.
Coloración de bordes El gráfico de Tietze requiere cuatro colores; es decir, su índice cromático es 4. De manera equivalente, los bordes del gráfico de Tietze se pueden dividir en cuatro coincidencias , pero no menos.
El gráfico de Tietze coincide con parte de la definición de snark : es un gráfico cúbico sin puentes que no se puede colorear en 3 bordes. Sin embargo, la mayoría de los autores restringen los snarks a gráficos sin 3 ciclos, por lo que generalmente no se considera que el gráfico de Tietze sea un snark. Sin embargo, es isomorfo al gráfico J 3 , parte de una familia infinita de snarks florales introducida por R. Isaacs en 1975. [5]
A diferencia del gráfico de Petersen, el gráfico de Tietze puede cubrirse mediante cuatro coincidencias perfectas . Esta propiedad juega un papel clave en la prueba de que probar si un gráfico puede cubrirse con cuatro coincidencias perfectas es NP-completo . [6]
La gráfica de Tietze tiene número cromático 3, índice cromático 4, circunferencia 3 y diámetro 3. El número de independencia es 5. Su grupo de automorfismo tiene orden 12, y es isomorfo al grupo diédrico D 6 , el grupo de simetrías de un hexágono , incluyendo a ambos. rotaciones y reflexiones. Este grupo tiene dos órbitas de tamaño 3 y una de tamaño 6 en los vértices y, por lo tanto, esta gráfica no es transitiva por vértices .
