Cintura (teoría de grafos)

En teoría de grafos, la cintura^[1] (en inglés girth) de un grafo no dirigido es la longitud del ciclo más corto contenido en dicho grafo.^[2] Si el grafo no posee ciclos (es decir, es un grafo acíclico), su cintura se define como infinita.^[3]

Por ejemplo, un ciclo de cuatro vértices (cuadrado) tiene cintura 4. Un látice cuadrado tiene cintura 4. Una malla triangular tiene cintura 3. Si un grafo tiene cintura mayor a tres, se dice que es libre de triángulos.

• 
  El grafo de Petersen tiene cintura 5
• 
  El grafo de Heawood tiene cintura de 6
• 
  El grafo de McGee tiene cintura 7
• 
  El grafo de Tutte-Coxeter tiene cintura 8

Cintura y coloraciones de grafos

Para cualesquiera enteros positivos ${\displaystyle g}$ y ${\displaystyle \chi }$, existe un grafo con cintura al menos ${\displaystyle g}$ y número cromático al menos ${\displaystyle \chi }$; por ejemplo, el grafo de Grotzsch es libre de triángulos y tiene número cromático 4. Más aún, si repetimos la construcción de Mycielskian en el grafo de Grotzsch, obtendremos grafos libres de triángulos con números cromáticos arbitrariamente largos. Paul Erdos fue el primero en probar este resultado, mediante el uso del método probabilístico.

Generalizaciones

La cintura par y cintura impar de un grafo son las longitudes del menor ciclo par e impar, respectivamente.

Referencias

1. Reinaldo Giudici y Ángeles Bris, Introducción a la teoría de grafos, p. 60. Ediciones de la Universidad Simón Bolívar
2. R. Diestel, Graph Theory, p.8. 3.ª Edición, Springer-Verlag, 2005
3. Girth -- Wolfram MathWorld.

• Datos: Q959831