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 y el grafo bipartito completo . 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 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 ReferenciaBosquesBucles, pares de aristas paralelas, y ciclos de todas las longitudesSubgrafoDefiniciónUn bucle (para multigrafos) o triángulos K3 (para grafos simples)Menor del grafoDefiniciónBosques lineales[Un bucle / triángulo K3 (véase arriba)] y estrella K1,3Menor del grafoDefiniciónGrafo libre de garrasEstrella K1,3Subgrafo inducidoDefiniciónGrafos comparablesSubgrafo inducidoGrafos sin triángulosTriángulo K3Subgrafo inducidoDefiniciónGrafos planosK5 y K3,3Subgrafo homeomorfoTeorema de KuratowskiK5 y K3,3Menor del grafoTeorema de WagnerGrafos planos exterioresK4 y K2,3Menor del grafo,. p. 107Grafos 1-planos externosSeis menores prohibidosMenor del grafo.Grafos de genus fijoUn conjunto finito de obstruccionesMenor del grafo, p. 275Grafos de ápiceUn conjunto finito de obstruccionesMenor del grafo.Grafos embebidos sin enlacesLa familia de PetersenMenor del grafo.Grafos bipartitosCiclos imparesSubgrafoBéla Bollobás (1998) "Modern Graph Theory", Springer, p. 9Grafos cordalesCiclos de longitud 4 o másSubgrafo inducido.Grafos perfectosCiclos de longitud impar 5 o más o sus complementosSubgrafo inducido.Grafo rectilíneo de grafos9 subgrafos prohibidosSubgrafo inducido.Uniones de grafos de grafos cactusEl grafo diamante de cuatro vértices formado al quitar una arista del grafo completo K4Menor del grafo.Grafos de escaleraK2,3 y su grafo dualSubgrafo homeomorfo.Grafos divididosSubgrafo inducido2-conexo serie-paralelo (ancho de árbol ≤ 2, ancho de rama≤ 2)K4Menor del grafo, p. 327Ancho de árbol ≤ 3K5, octaedro, prisma pentagonal, grafo de WagnerMenor del grafo.Ancho de rama ≤ 3K5, octaedro, cubo, grafo de WagnerMenor del grafo.Grafos reducibles por complemento (cografos)4-vértices recorrido P4Subgrafo inducidoGrafos perfectos trivialmente4-vértices recorrido P4 y 4-vértices ciclo C4Subgrafo inducido.Grafos umbral4-vértices recorrido P4, 4-vértices ciclo C4 y complemento de C4Subgrafo inducidoGrafo con rectas de 3-uniforme hipergrafos con rectasUna lista finita de subgrafos inducidos prohibidos con un grado mínimo de al menos 19Subgrafo inducidoGrafo con rectas de k-uniforme hipergrafos con rectas, k > 3Una lista finita de subgrafos inducidos prohibidos con grado de arista mínimo al menos 2k2 − 3k + 1Subgrafo inducidoGrafos ΔY-reducibles a un solo vérticeUna lista finita de al menos 68 mil millones de sumas distintas de (1,2,3)-clicasMenor del grafo WebsiteTeoremas generalesUna familia definida por una propiedad inducida-hereditariaUn, posiblemente no-finito, conjunto de obstruccionesSubgrafo inducidoUna familia definida por una propiedad de menor-hereditariaUn conjunto finito de obstruccionesMenor del grafoTeorema de Robertson-Seymour
Véase también Conjetura de Erdős-Hajnal Problema del subgrafo prohibido Menor matroide Problema de Zarankiewicz
Referencias
Categoría:Teoría de grafos Categoría:Menor en teoría de grafos Categoría:Familias de grafos Categoría:Teoría de hipergrafos