Cintura (teoria dos grafos)

Em teoria dos grafos a cintura ou girth de um grafo é o comprimento do mais curto ciclo contido no grafo. Se o grafo não contém ciclos (isto é, um grafo acíclico), a sua cintura é definida como infinita. Por exemplo, um 4-ciclo (quadrado), tem cintura 4. Uma grade tem cintura 4, igualmente, e uma malha triangular tem cintura 3. Um grafo com cintura >3 é livre de triângulos.

Gaiolas

Um grafo cúbico (todos os vértices tem grau três) de cintura $g$ que é tão pequeno quanto possível, é conhecido como uma gaiola-$g$ (ou como uma (3,g)-gaiola). O grafo de Petersen é o único gaiola-5 (esse é o menor grafo cúbico de cintura 5), o grafo de Heawood é o único gaiola-6, o grafo de McGee é o único gaiola-7 e o gaiola oito de Tutte é o único gaiola-8. Podem existir várias gaiolas para uma cintura dada. Por exemplo, há três gaiolas-10 não-isomórficas, cada uma com 70 vértices: a gaiola-10 de Balaban, o grafo de Harries e o grafo de Harries-Wong.

• 
  O grafo de Petersen tem cintura 5
• 
  O grafo de Heawood tem cintura 6
• 
  O grafo de McGee tem cintura 7
• 
  A gaiola oito de Tutte tem cintura 8

Cintura e coloração de grafos

Para quaisquer inteiros positivos g e χ, existe um grafo com cintura de pelo menos g e número cromático, de pelo menos χ; por exemplo, o grafo de Grötzsch é livre de triângulo e tem número cromático 4, e repetindo a construção de Mycielskian usada para formar o grafo de Grötzsch produz grafos livres de triângulos de arbitrariamente grande número cromático. Paul Erdős foi o primeiro a provar o resultado geral, usando o método probabilístico. Uma prova construtiva desse teorema foi dada por Lovász em 1968.

Mais precisamente, ele mostrou que um grafo aleatório em n vértices, formado por escolha independentemente se é necessário incluir cada aresta com probabilidade n^{(1 − g)/g}, tem, com probabilidade tendendo a 1 a medida que n vai para o infinito, no máximo n/2 ciclos de comprimento g ou menos, mas não tem nenhum conjunto independente de tamanho n/2k. Portanto, a remoção de um vértice de cada ciclo curto deixa um pequeno grafo com cintura superior a g, em que cada classe de cor de uma coloração deve ser pequena e que, portanto, exige, pelo menos k cores em qualquer coloração.

Generalizações

A cintura ímpar e a cintura par de um grafo são o comprimento do ciclo ímpar mais curto e o ciclo par mais curto respectivamente. Pensada como o menor comprimento de um ciclo não-trivial, a cintura admite generalizações naturais como a 1-sístole ou maiores sístoles em geometria sistólica.