Caracterización de grafos prohibidos

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

Un ejemplo prototípico de este fenómeno es _el teorema de Kuratowski , que establece que un grafo es planar (puede dibujarse 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₃ _,₃ . Para el teorema de Kuratowski, la noción de contención es la de homeomorfismo de grafos , en la que una subdivisión de un grafo aparece como subgrafo del otro. Por lo tanto, todo grafo tiene un dibujo planar (en cuyo caso pertenece a la familia de grafos planares) o bien tiene una subdivisión de al menos uno de estos dos grafos como subgrafo (en cuyo caso no pertenece a los grafos planares).

En términos más generales, una caracterización de grafo prohibido es un método para especificar una familia de estructuras de grafos o hipergrafos , especificando subestructuras que están prohibidas 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.${\displaystyle {\mathcal {F}}}$si y solo si una subestructura prohibida no está contenida en G. La subestructura prohibida podría ser una de las siguientes:

• subgrafos , grafos más pequeños obtenidos a partir de subconjuntos de los vértices y aristas de un grafo más grande,
• subgrafos inducidos , grafos más pequeños obtenidos al seleccionar un subconjunto de los vértices y usar todas las aristas con ambos extremos en ese subconjunto,
• subgrafos homeomorfos (también llamados menores topológicos ), grafos más pequeños obtenidos a partir de subgrafos colapsando caminos de vértices de grado dos a aristas únicas, o
• grafos menores , grafos más pequeños obtenidos a partir de subgrafos mediante contracciones de aristas arbitrarias .

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

Las caracterizaciones de grafos prohibidos pueden utilizarse en algoritmos para determinar si un grafo pertenece a una familia determinada. En muchos casos, es posible comprobar en tiempo polinomial si un grafo dado contiene alguno de los elementos del conjunto de obstrucciones y, por lo tanto, si pertenece a la familia definida por dicho conjunto.

Para que una familia tenga una caracterización de grafo prohibida, con un tipo particular de subestructura, debe ser cerrada bajo subestructuras. Es decir, toda subestructura (de un tipo dado) de un grafo en la familia debe ser otro grafo en la familia. De forma equivalente, si un grafo no forma parte de la familia, todos los grafos mayores que lo contienen como subestructura también deben quedar excluidos de la familia. Cuando esto se cumple, siempre existe un conjunto de obstrucción (el conjunto de grafos que no pertenecen a la familia, pero cuyas subestructuras menores sí pertenecen a ella). Sin embargo, para ciertas nociones de lo que es una subestructura, este conjunto de obstrucción podría ser infinito. El teorema de Robertson-Seymour demuestra que, para el caso particular de los menores de grafos , una familia que es cerrada bajo menores siempre tiene un conjunto de obstrucción finito.

• Conjetura de Erdős-Hajnal
• Problema del subgrafo prohibido
• Matroid menor
• Problema de Zarankiewicz