stringtranslate.com

Caracterización de gráficos prohibidos.

En 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, además, excluyen todos los grafos de la familia que contengan cualquiera de estos grafos prohibidos como (inducidos). subgrafo o menor .

Un ejemplo prototípico de este fenómeno es el teorema de Kuratowski , que establece que una gráfica es plana (puede dibujarse sin cruces en el plano) si y sólo si no contiene ninguna de las dos gráficas prohibidas, la gráfica completa K 5 y la bipartita completa. gráfica K 3,3 . Para el teorema de Kuratowski, la noción de contención es la de homeomorfismo de grafos , en el que una subdivisión de un grafo aparece como un subgrafo del otro. Así, todo grafo 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 grafo prohibido es un método para especificar una familia de estructuras de grafo , o hipergrafo , especificando 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 sólo si una subestructura prohibida no está contenida en G. La subestructura prohibida podría ser una de:

El conjunto de estructuras a las que se les prohíbe pertenecer a una familia de grafos determinada también se puede denominar conjunto de obstrucción para esa familia.

Las caracterizaciones de gráficos prohibidas se pueden utilizar en algoritmos para probar si un gráfico pertenece a una familia determinada. En muchos casos, es posible probar en tiempo polinómico si un gráfico dado contiene alguno de los miembros del conjunto de obstrucción y, por tanto, si pertenece a la familia definida por ese conjunto de obstrucción.

Para que una familia tenga una caracterización de grafo prohibido, con un tipo particular de subestructura, la familia debe estar cerrada bajo subestructuras. Es decir, cada subestructura (de un tipo determinado) de un grafo de la familia debe ser otro grafo de la familia. De manera equivalente, si un gráfico no es parte de la familia, todos los gráficos más grandes que lo contengan como subestructura también deben excluirse de la familia. Cuando esto es cierto, siempre existe un conjunto de obstrucciones (el conjunto de gráficos 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 demuestra que, para el caso particular de grafos menores , una familia cerrada bajo menores siempre tiene un conjunto de obstrucciones finito.

Lista de caracterizaciones prohibidas para gráficos e hipergráficos.

Ver también

Referencias

  1. ^ abc Diestel, Reinhard (2000), Teoría de grafos , Textos de posgrado en matemáticas, vol. 173, Springer-Verlag, ISBN 0-387-98976-5.
  2. ^ Auer, Cristóbal; Bachmaier, cristiano; Brandeburgo, Franz J.; Gleissner, Andreas; Hanauer, Kathrin; Neuwirth, Daniel; Reislhuber, Josef (2013), "Reconocimiento de gráficos uniplanares externos en tiempo lineal", en Wismath, Stephen; Wolff, Alexander (eds.), 21.er Simposio Internacional, GD 2013, Burdeos, Francia, 23 al 25 de septiembre de 2013, artículos seleccionados revisados , Lecture Notes in Computer Science, vol. 8242, págs. 107–118, doi : 10.1007/978-3-319-03841-4_10.
  3. ^ Gupta, A.; Impagliazzo, R. (1991), "Computación de entrelazamientos planos", Proc. 32º Simposio IEEE sobre fundamentos de la informática (FOCS '91) , IEEE Computer Society, págs. 802–811, doi :10.1109/SFCS.1991.185452, S2CID  209133.
  4. ^ Robertson, Neil ; Seymour, PD ; Thomas, Robin (1993), "Incrustaciones sin enlaces de gráficos en 3 espacios", Boletín de la Sociedad Matemática Estadounidense , 28 (1): 84–89, arXiv : math/9301216 , doi :10.1090/S0273-0979-1993- 00335-5, SEÑOR  1164063, S2CID  1110662.
  5. ^ Béla Bollobás (1998) "Teoría de grafos moderna", Springer, ISBN 0-387-98488-7 p. 9 
  6. ^ Kashiwabara, Toshinobu (1981), "Algoritmos para algunos gráficos de intersección", en Saito, Nobuji; Nishizeki, Takao (eds.), Teoría de grafos y algoritmos, 17º Simposio del Instituto de Investigación de Comunicaciones Eléctricas, Universidad de Tohoku, Sendai, Japón, 24 y 25 de octubre de 1980, Actas , Lecture Notes in Computer Science, vol. 108, Springer-Verlag, págs. 171–181, doi : 10.1007/3-540-10704-5_15.
  7. ^ Chudnovsky, María ; Robertson, Neil ; Seymour, Pablo ; Thomas, Robin (2006), "El teorema del grafo perfecto fuerte" (PDF) , Annals of Mathematics , 164 (1): 51–229, arXiv : math/0212070v1 , doi :10.4007/annals.2006.164.51, S2CID  119151552.
  8. ^ Beineke, LW (1968), "Gráficos derivados de dígrafos", en Sachs, H.; Voss, H.-J.; Walter, H.-J. (eds.), Beiträge zur Graphentheorie , Leipzig: Teubner, págs. 17-33.
  9. ^ El-Mallah, Ehab; Colbourn, Charles J. (1988), "La complejidad de algunos problemas de eliminación de bordes", IEEE Transactions on Circuits and Systems , 35 (3): 354–362, doi :10.1109/31.1748.
  10. ^ Takamizawa, K.; Nishizeki, Takao ; Saito, Nobuji (1981), "Problemas combinatorios en gráficos en series-paralelas", Matemáticas aplicadas discretas , 3 (1): 75–76, doi : 10.1016/0166-218X(81)90031-7.
  11. ^ Földes, Stéphane; Hammer, Peter Ladislaw (1977a), "Split Graphs", Actas de la Octava Conferencia del Sureste sobre Combinatoria, Teoría de Grafos y Computación (Louisiana State Univ., Baton Rouge, Luisiana, 1977) , Congressus Numerantium, vol. XIX, Winnipeg: Utilitas Math., págs. 311–315, SEÑOR  0505860
  12. ^ Bodlaender, Hans L. (1998), "Un k -arboreto parcial de gráficos con ancho de árbol acotado", Ciencias de la Computación Teórica , 209 (1–2): 1–45, doi :10.1016/S0304-3975(97)00228- 4, hdl : 1874/18312.
  13. ^ Bodlaender, Hans L .; Thilikos, Dimitrios M. (1999), "Gráficos con ancho de rama como máximo tres", Journal of Algorithms , 32 (2): 167–194, doi :10.1006/jagm.1999.1011, hdl : 1874/2734.
  14. ^ Seinsche, D. (1974), "Sobre una propiedad de la clase de n -gráficos coloreables", Journal of Combinatorial Theory , Serie B, 16 (2): 191–193, doi : 10.1016/0095-8956(74) 90063-X , señor  0337679
  15. ^ ab Golumbic, Martin Charles (1978), "Gráficos trivialmente perfectos", Matemáticas discretas , 24 (1): 105–107, doi : 10.1016/0012-365X(78)90178-4.
  16. ^ Metelsky, Yuri; Tyshkevich, Regina (1997), "Gráficos en línea de hipergráficos lineales de 3 uniformes", Journal of Graph Theory , 25 (4): 243–251, doi :10.1002/(SICI)1097-0118(199708)25:4< 243::AID-JGT1>3.0.CO;2-K, SEÑOR  1459889
  17. ^ Jacobson, MS; Kézdy, Andre E.; Lehel, Jeno (1997), "Reconocimiento de gráficas de intersección de hipergrafías lineales uniformes", Graphs and Combinatorics , 13 (4): 359–367, doi :10.1007/BF03353014, MR  1485929, S2CID  9173731
  18. ^ Naik, Ranjan N.; Rao, SB; Shrikhande, SS ; Singhi, NM (1982), "Gráficos de intersección de k -hipergrafos uniformes", European Journal of Combinatorics , 3 : 159–172, doi : 10.1016/s0195-6698(82)80029-2 , MR  0670849
  19. ^ Yu, Yanming (2006), "Más menores prohibidos para la reducibilidad estrella-delta-estrella", The Electronic Journal of Combinatorics , 13 , doi : 10.37236/1033Sitio web
  20. ^ Jiang, Zilin; Polyanskii, Alexandr (1 de marzo de 2020). "Subgrafos prohibidos para gráficos de radio espectral acotado, con aplicaciones a líneas equiangulares". Revista Israelí de Matemáticas . 236 (1): 393–421. arXiv : 1708.02317 . doi :10.1007/s11856-020-1983-2. ISSN  1565-8511.