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₅ 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
	Un bucle (para multigrafos) o triángulos K3 (para grafos simples)	Menor del grafo	Definición
Bosques lineales	[Un bucle / triángulo K3 (véase arriba)] y estrella K1,3	Menor del grafo	Definición
Grafo libre de garras	Estrella K1,3	Subgrafo inducido	Definición
Grafos comparables		Subgrafo inducido
Grafos sin triángulos	Triángulo K3	Subgrafo inducido	Definición
Grafos planos	K5 y K3,3	Subgrafo homeomorfo	Teorema de Kuratowski
	K5 y K3,3	Menor del grafo	Teorema de Wagner
Grafos planos exteriores	K4 y K2,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 K4	Menor del grafo	​
Grafos de escalera	K2,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)	K4	Menor del grafo	Diestel (2000),​ p. 327
Ancho de árbol ≤ 3	K5, octaedro, prisma pentagonal, grafo de Wagner	Menor del grafo	​
Ancho de rama ≤ 3	K5, octaedro, cubo, grafo de Wagner	Menor del grafo	​
Grafos reducibles por complemento (cografos)	4-vértices recorrido P4	Subgrafo inducido	​
Grafos perfectos trivialmente	4-vértices recorrido P4 y 4-vértices ciclo C4	Subgrafo inducido	​
Grafos umbral	4-vértices recorrido P4, 4-vértices ciclo C4 y complemento de C4	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 2k2 − 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

Véase también

• Conjetura de Erdős-Hajnal
• Problema del subgrafo prohibido
• Menor matroide
• Problema de Zarankiewicz

Referencias

• Datos: Q5467387