Caracterización de grafos prohibidos
# Caracterización de grafos prohibidos

En teoría de grafos, una rama de las matemáticas, muchas familias importantes de grafos se pueden describir mediante un conjunto finito de grafos individuales que no pertenecen a la familia y además excluyen todos los grafos de la familia que contienen cualquiera de estos grafos prohibidos como subgrafos o menores (inducidos).

Un ejemplo prototípico de este fenómeno es el teorema de Kuratowski, que establece que un grafo es plano (es decir, se puede dibujar sin cruces en el plano) si y solo si no contiene ninguno de los dos grafos prohibidos, el grafo completo $K_5$ y el grafo bipartito completo $K_{3,3}.$ Para el teorema de Kuratowski, la noción de contener es la del homeomorfismo de grafos, en la que una subdivisión de un grafo aparece como subgrafo del otro. Así, todo grafo o bien tiene un dibujo plano (en cuyo caso pertenece a la familia de los grafos planos) o tiene una subdivisión de al menos uno de estos dos grafos como subgrafo (en cuyo caso no pertenece a los grafos planos).

## Definición

De manera más general, una caracterización de grafos prohibidos es un método de identificar una familia de estructuras de grafos o hipergrafos, mediante la especificación de subestructuras cuya existencia está prohibida dentro de cualquier grafo de la familia. Las diferentes familias varían en la naturaleza de lo que está prohibido. En general, una estructura G es miembro de una familia ${\mathcal {F}}$ si y solo si una subestructura prohibida no está contenida en G. Las subestructuras prohibidas podrían ser:

* Subgrafos, grafos más pequeños obtenidos a partir de subconjuntos de vértices y aristas de un grafo más grande.
* Subgrafos inducidos, grafos más pequeños obtenidos seleccionando un subconjunto de los vértices y usando todas las aristas con ambos extremos en ese subconjunto.
* Subgrafos homeomorfos (también llamados menores), grafos más pequeños obtenidos a partir de subgrafos al colapsar caminos de vértices de grado dos en aristas simples.
* Menores, grafos más pequeños obtenidos de subgrafos por contracción de aristas arbitrarias.

El conjunto de estructuras que tienen prohibido pertenecer a una familia de grafos dada también puede denominarse conjunto de obstrucciones para esa familia.

Las caracterizaciones de grafos prohibidos se pueden usar en algoritmia para probar si un grafo pertenece a una familia determinada. En muchos casos, es posible probar en tiempo polinómico si un grafo dado contiene alguno de los miembros del conjunto de obstrucciones y, por lo tanto, si pertenece a la familia definida por este conjunto.

Para que una familia tenga una caracterización gráfica prohibida, con un tipo particular de subestructura, la familia debe estar cerrada bajo subestructuras, es decir, cada subestructura (de un tipo dado) de un grafo de la familia debe ser otro grafo de la familia. De manera equivalente, si un grafo no es parte de la familia, todos los grafos más grandes que lo contengan como subestructura también deben excluirse de la familia. Cuando esto es cierto, siempre existe un conjunto de obstrucción (el conjunto de grafos que no están en la familia pero cuyas subestructuras más pequeñas pertenecen todas a la familia). Sin embargo, para algunas nociones de lo que es una subestructura, este conjunto de obstrucciones podría ser infinito. El teorema de Robertson-Seymour prueba que, para el caso particular de los menores, una familia cerrada por menores siempre tiene un conjunto finito de obstrucciones.

## Lista de caracterizaciones prohibidas para grafos e hipergrafos

| Familia | Obstrucciones | Relación | Referencia |
| - | - | - | - |
| Bosques | Bucles, pares de aristas paralelas, y ciclos de todas las longitudes | Subgrafo | Definición |
| Bosques | Un bucle (para multigrafos) o triángulos $K_3$ (para grafos simples) | Menor del grafo | Definición |
| Bosques lineales | [Un bucle / triángulo $K_3$ (véase arriba)] y estrella $K_{1,3}$ | Menor del grafo | Definición |
| Grafo libre de garras | Estrella $K_{1,3}$ | Subgrafo inducido | Definición |
| Grafos comparables | | Subgrafo inducido | |
| Grafos sin triángulos | Triángulo $K_3$ | Subgrafo inducido | Definición |
| Grafos planos | $K_5$ y $K_{3,3}$ | Subgrafo homeomorfo | Teorema de Kuratowski |
| Grafos planos | $K_5$ y $K_{3,3}$ | Menor del grafo | Teorema de Wagner |
| Grafos planos exteriores | $K_4$ y $K_{2,3}$ | Menor del grafo | Diestel (2000), p. 107 |
| Grafos 1-planos externos | Seis menores prohibidos | Menor del grafo | Auer et al. (2013) |
| Grafos de genus fijo | Un conjunto finito de obstrucciones | Menor del grafo | Diestel (2000), p. 275 |
| Grafos de ápice | Un conjunto finito de obstrucciones | Menor del grafo | |
| Grafos embebidos sin enlaces | La familia de Petersen | Menor del grafo | |
| Grafos bipartitos | Ciclos impares | Subgrafo | |
| Grafos cordales | Ciclos de longitud 4 o más | Subgrafo inducido | |
| Grafos perfectos | Ciclos de longitud impar 5 o más o sus complementos | Subgrafo inducido | |
| Grafo rectilíneo de grafos | 9 subgrafos prohibidos | Subgrafo inducido | |
| Uniones de grafos de grafos cactus | El grafo diamante de cuatro vértices formado al quitar una arista del grafo completo $K_4$ | Menor del grafo | |
| Grafos de escalera | $K_{2,3}$ y su grafo dual | Subgrafo homeomorfo | |
| Grafos divididos | $C_{4},C_{5},{\bar {C}}_{4}\left(=K_{2}+K_{2}\right)$ | Subgrafo inducido | |
| 2-conexo serie-paralelo (ancho de árbol ≤ 2, ancho de rama ≤ 2) | $K_4$ | Menor del grafo | Diestel (2000), p. 327 |
| Ancho de árbol ≤ 3 | $K_5,$ octaedro, prisma pentagonal, grafo de Wagner | Menor del grafo | |
| Ancho de rama ≤ 3 | $K_5,$ octaedro, cubo, grafo de Wagner | Menor del grafo | |
| Grafos reducibles por complemento (cografos) | 4-vértices recorrido $P_4$ | Subgrafo inducido | |
| Grafos perfectos trivialmente | 4-vértices recorrido $P_4$ y 4-vértices ciclo $C_4$ | Subgrafo inducido | |
| Grafos umbral | 4-vértices recorrido $P_4,$ 4-vértices ciclo $C_4$ y complemento de $C_4$ | Subgrafo inducido | |
| Grafo con rectas de 3-uniforme hipergrafos con rectas | Una lista finita de subgrafos inducidos prohibidos con un grado mínimo de al menos 19 | Subgrafo inducido | |
| Grafo con rectas de k-uniforme hipergrafos con rectas, k > 3 | Una lista finita de subgrafos inducidos prohibidos con grado de arista mínimo al menos $2k^2$ − 3k + 1 | Subgrafo inducido | |
| Grafos ΔY-reducibles a un solo vértice | Una lista finita de al menos 68 mil millones de sumas distintas de (1,2,3)-clicas | Menor del grafo | |
| Teoremas generales ||||
| Una familia definida por una propiedad inducida-hereditaria | Un, posiblemente no-finito, conjunto de obstrucciones | Subgrafo inducido | |
| Una familia definida por una propiedad de menor-hereditaria | Un conjunto finito de obstrucciones | Menor del grafo | Teorema de Robertson-Seymour |
