Ver el código de «Cintura (teoría de grafos)»

En [[teoría de grafos]], la '''cintura'''<ref>Reinaldo Giudici y Ángeles Bris, ''[http://books.google.com/books?id=0MqeE30_C6cC Introducción a la teoría de grafos]'', p. 60. Ediciones de la Universidad Simón Bolívar</ref> (en inglés '''girth''') de un [[grafo]] no dirigido es la longitud del [[grafo ciclo|ciclo]] más corto contenido en dicho grafo.<ref>R. Diestel, ''Graph Theory'', p.8. 3.ª Edición, Springer-Verlag, 2005</ref> Si el grafo no posee ciclos (es decir, es un grafo acíclico), su cintura se define como [[infinita]].<ref>{{Obra citada|url=http://mathworld.wolfram.com/Girth.html|title=Girth -- Wolfram MathWorld}}</ref>

Por ejemplo, un ciclo de cuatro [[vértice (teoría de grafos)|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.

<gallery>
Archivo:Petersen1 tiny.svg|El [[grafo de Petersen]] tiene cintura 5
Archivo:Heawood_Graph.svg|El [[grafo de Heawood]] tiene cintura de 6
Archivo:McGee graph.svg|El [[grafo de McGee]] tiene cintura 7
Archivo:Tutte eight cage.svg|El [[grafo de Tutte-Coxeter]] tiene cintura 8
</gallery>

== Cintura y coloraciones de grafos ==
Para cualesquiera enteros positivos <math>g</math> y <math>\chi</math>, existe un grafo con cintura al menos <math>g</math> y número cromático al menos <math>\chi</math>; 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 Erdős|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 ==
{{listaref}}

{{Control de autoridades}}
[[Categoría:Teoría de grafos]]
[[Categoría:Invariantes de grafos]]