En el campo matemático de la teoría de grafos , el grafo de Franklin es un grafo regular de 3 ejes con 12 vértices y 18 aristas.
El grafo de Franklin recibe su nombre de Philip Franklin , quien refutó la conjetura de Heawood sobre el número de colores necesarios cuando una superficie bidimensional se divide en celdas mediante una incrustación de grafos . [1] La conjetura de Heawood implicaba que el número cromático máximo de un mapa en la botella de Klein debería ser siete, pero Franklin demostró que en este caso siempre son suficientes seis colores. (La botella de Klein es la única superficie para la que falla la conjetura de Heawood). El grafo de Franklin se puede incrustar en la botella de Klein de modo que forme un mapa que requiera seis colores, lo que demuestra que a veces son necesarios seis colores en este caso. Esta incrustación es el dual de Petrie de su incrustación en el plano proyectivo que se muestra a continuación.
Es hamiltoniano y tiene número cromático 2, índice cromático 3, radio 3, diámetro 3 y circunferencia 4. También es un grafo perfecto conexo por 3 vértices y conexo por 3 aristas .
El grupo de automorfismos del grafo de Franklin es de orden 48 y es isomorfo a Z /2 Z × S 4 , el producto directo del grupo cíclico Z /2 Z y el grupo simétrico S 4 . Actúa transitivamente sobre los vértices del grafo, haciéndolo transitivo-vertical .
El polinomio característico del gráfico de Franklin es
