Cintura (teoría de grafos)

longitud del ciclo más corto contenido en un grafo

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 contura mayor a tres, se dice que es libre de triángulos.

Cintura y coloraciones de grafosEditar

Para cualesquiera enteros positivos   y  , existe un grafo con cintura al menos   y número cromático al menos  ; 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.

GeneralizacionesEditar

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

ReferenciasEditar

  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 .