Caracterización de grafos prohibidos

describir una familia de grafos excluyendo ciertos (sub)grafos
(Redirigido desde «Menores 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 K5 y el grafo bipartito completo K3,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

editar

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

editar
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),[1]p. 107
Grafos 1-planos externos Seis menores prohibidos Menor del grafo Auer et al. (2013)[2]
Grafos de genus fijo Un conjunto finito de obstrucciones Menor del grafo Diestel (2000),[1]p. 275
Grafos de ápice Un conjunto finito de obstrucciones Menor del grafo [3]
Grafos embebidos sin enlaces La familia de Petersen Menor del grafo [4]
Grafos bipartitos Ciclos impares Subgrafo [5]
Grafos cordales Ciclos de longitud 4 o más Subgrafo inducido [6]
Grafos perfectos Ciclos de longitud impar 5 o más o sus complementos Subgrafo inducido [7]
Grafo rectilíneo de grafos 9 subgrafos prohibidos Subgrafo inducido [8]
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 [9]
Grafos de escalera K2,3 y su grafo dual Subgrafo homeomorfo [10]
Grafos divididos   Subgrafo inducido [11]
2-conexo serie-paralelo (ancho de árbol ≤ 2, ancho de rama ≤ 2) K4 Menor del grafo Diestel (2000),[1]p. 327
Ancho de árbol ≤ 3 K5, octaedro, prisma pentagonal, grafo de Wagner Menor del grafo [12]
Ancho de rama ≤ 3 K5, octaedro, cubo, grafo de Wagner Menor del grafo [13]
Grafos reducibles por complemento (cografos) 4-vértices recorrido P4 Subgrafo inducido [14]
Grafos perfectos trivialmente 4-vértices recorrido P4 y 4-vértices ciclo C4 Subgrafo inducido [15]
Grafos umbral 4-vértices recorrido P4, 4-vértices ciclo C4 y complemento de C4 Subgrafo inducido [15]
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 [16]
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 [17][18]
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 [19]
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

editar

Referencias

editar
  1. a b c Diestel, Reinhard (2000), Graph Theory, Graduate Texts in Mathematics 173, Springer-Verlag, ISBN 0-387-98976-5 ..
  2. Auer, Christopher; Bachmaier, Christian; Brandenburg, Franz J.; Gleißner, Andreas; Hanauer, Kathrin; Neuwirth, Daniel; Reislhuber, Josef (2013), «Recognizing outer 1-planar graphs in linear time», en Wismath, Stephen; Wolff, Alexander, eds., 21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers, Lecture Notes in Computer Science 8242, pp. 107-118, doi:10.1007/978-3-319-03841-4_10 ..
  3. Gupta, A.; Impagliazzo, R. (1991), «Computing planar intertwines», Proc. 32nd IEEE Symposium on Foundations of Computer Science (FOCS '91), IEEE Computer Society, pp. 802-811, S2CID 209133, doi:10.1109/SFCS.1991.185452 ..
  4. Robertson, Neil; Seymour, P. D.; Thomas, Robin (1993), «Linkless embeddings of graphs in 3-space», Bulletin of the American Mathematical Society 28 (1): 84-89, MR 1164063, S2CID 1110662, arXiv:math/9301216, doi:10.1090/S0273-0979-1993-00335-5 ..
  5. Béla Bollobás (1998) "Modern Graph Theory", Springer, ISBN 0-387-98488-7 p. 9
  6. Kashiwabara, Toshinobu (1981), «Algorithms for some intersection graphs», en Saito, Nobuji; Nishizeki, Takao, eds., Graph Theory and Algorithms, 17th Symposium of Research Institute of Electric Communication, Tohoku University, Sendai, Japan, October 24-25, 1980, Proceedings, Lecture Notes in Computer Science 108, Springer-Verlag, pp. 171-181, doi:10.1007/3-540-10704-5_15 ..
  7. Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006), «The strong perfect graph theorem», Annals of Mathematics 164 (1): 51-229, S2CID 119151552, arXiv:math/0212070v1, doi:10.4007/annals.2006.164.51 ..
  8. Beineke, L. W. (1968), «Derived graphs of digraphs», en Sachs, H.; Voss, H.-J.; Walter, H.-J., eds., Beiträge zur Graphentheorie, Leipzig: Teubner, pp. 17-33 ..
  9. El-Mallah, Ehab; Colbourn, Charles J. (1988), «The complexity of some edge deletion problems», IEEE Transactions on Circuits and Systems 35 (3): 354-362, doi:10.1109/31.1748 ..
  10. Takamizawa, K.; Nishizeki, Takao; Saito, Nobuji (1981), «Combinatorial problems on series–parallel graphs», Discrete Applied Mathematics 3 (1): 75-76, doi:10.1016/0166-218X(81)90031-7 ..
  11. Földes, Stéphane; Hammer, Peter Ladislaw (1977a), «Split graphs», Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977), Congressus Numerantium XIX, Winnipeg: Utilitas Math., pp. 311-315, MR 0505860 .
  12. Bodlaender, Hans L. (1998), «A partial k-arboretum of graphs with bounded treewidth», Theoretical Computer Science 209 (1–2): 1-45, doi:10.1016/S0304-3975(97)00228-4, hdl:1874/18312 ..
  13. Bodlaender, Hans L.; Thilikos, Dimitrios M. (1999), «Graphs with branchwidth at most three», Journal of Algorithms 32 (2): 167-194, doi:10.1006/jagm.1999.1011, hdl:1874/2734 ..
  14. Seinsche, D. (1974), «On a property of the class of n-colorable graphs», Journal of Combinatorial Theory, Series B 16 (2): 191-193, MR 0337679, doi:10.1016/0095-8956(74)90063-X .
  15. a b Golumbic, Martin Charles (1978), «Trivially perfect graphs», Discrete Mathematics 24 (1): 105-107, doi:10.1016/0012-365X(78)90178-4 ..
  16. Metelsky, Yury; Tyshkevich, Regina (1997), «On line graphs of linear 3-uniform hypergraphs», Journal of Graph Theory 25 (4): 243-251, MR 1459889, doi:10.1002/(SICI)1097-0118(199708)25:4<243::AID-JGT1>3.0.CO;2-K .
  17. Jacobson, M. S.; Kézdy, Andre E.; Lehel, Jeno (1997), «Recognizing intersection graphs of linear uniform hypergraphs», Graphs and Combinatorics 13 (4): 359-367, MR 1485929, S2CID 9173731, doi:10.1007/BF03353014 .
  18. Naik, Ranjan N.; Rao, S. B.; Shrikhande, S. S.; Singhi, N. M. (1982), «Intersection graphs of k-uniform hypergraphs», European Journal of Combinatorics 3: 159-172, MR 0670849, doi:10.1016/s0195-6698(82)80029-2 .
  19. Yu, Yanming (2006), «More forbidden minors for wye-delta-wye reducibility», The Electronic Journal of Combinatorics 13, doi:10.37236/1033 . Website