Grafo de Folkman

No campo da matemática da teoria dos grafos o grafo de Folkman, nomeado em honra a Jon Folkman, é um grafo bipartido 4-regular com 20 vértices e 40 arestas.

Grafo de Folkman
O grafo de Folkman
Nomeado em honra a	J. Folkman
vértices	20
arestas	40
Raio	3
Diâmetro	4
Cintura	4
Número cromático	2
Índice cromático	4
Propriedades	Perfeito Hamiltoniano Semi-simétrico Bipartido Regular Euleriano

O grafo de Folkman é Hamiltoniano e tem número cromático 2, índice cromático 4, raio 3, diâmetro 4 e cintura 4. e é um grafo perfeito tanto 4-vértice-conectado quanto 4-aresta-conectado.

Propriedades algébricas

O grupo de automorfismo do grafo de Folkman age transitivamente em suas arestas, mas não em seus vértices. É o menor grafo não direcionado, que é aresta-transitivo e regular, mas não é vértice-transitivo. Esses grafos são chamados semi-simétricos e foram estudados pela primeira vez por Folkman em 1967 que descobriu o grafo de 20 vértices, que agora é nomeado em sua honra.

Como um grafo semi-simétrico, o gráfico de Folkman é bipartido, e seu grupo de automorfismo age transitivamente em cada um dos dois conjuntos de vértices da bipartição. No diagrama abaixo, indicando o número cromático do grafo, os vértices verdes não podem ser mapeados para os vermelhos por qualquer automorfismo, mas qualquer vértice vermelho pode ser mapeado em qualquer outro vértice vermelho e qualquer vértice verde pode ser mapeado em qualquer outro vértice verde.

O polinômio característico do grafo de Folkman é $(x-4)x^{10}(x+4)(x^{2}-6)^{4}$.

Galeria

• 
  O índice cromático do grafo de Folkman é 4.
• 
  O número cromático do grafo de Folkman é 2.
• 
  O grafo de Folkman é Hamiltoniano.