stringtranslate.com

Caracterización de gráficos prohibida

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 además excluyen todos los grafos de la familia que contienen cualquiera de estos grafos prohibidos como subgrafos (inducidos) o menores .

Un ejemplo prototípico de este fenómeno es el teorema de Kuratowski , que establece que un grafo es plano (puede dibujarse sin cruces en el plano) si y solo si no contiene ninguno de los dos grafos prohibidos, el grafo completo K 5 y el grafo bipartito completo 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 subgrafo del otro. Así, todo grafo tiene un dibujo plano (en cuyo caso pertenece a la familia de 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

En términos más generales, 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 solo si una subestructura prohibida no está contenida en G. La subestructura prohibida podría ser una de las siguientes:

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

Las caracterizaciones de grafos prohibidos se pueden utilizar en algoritmos para comprobar si un grafo pertenece a una familia determinada. En muchos casos, es posible comprobar en tiempo polinómico si un grafo determinado contiene alguno de los miembros del conjunto de obstáculos y, por lo tanto, si pertenece a la familia definida por ese conjunto de obstáculos.

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 dado) de un grafo en la familia debe ser otro grafo en la familia. Equivalentemente, si un grafo no es parte de la familia, todos los grafos más grandes que lo contienen 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 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 está cerrada bajo menores siempre tiene un conjunto de obstrucción finito.

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

Véase 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 , ISBN 978-3-319-03840-7.
  3. ^ Gupta, A.; Impagliazzo, R. (1991), "La computación plana se entrelaza", Proc. 32.º Simposio IEEE sobre Fundamentos de la Ciencia de la Computación (FOCS '91) , IEEE Computer Society, págs. 802–811, doi :10.1109/SFCS.1991.185452, ISBN 0-8186-2445-0, S2CID209133 ​.
  4. ^ Robertson, Neil ; Seymour, PD ; Thomas, Robin (1993), "Incorporaciones sin enlaces de gráficos en el espacio tridimensional", Boletín de la Sociedad Matemática Americana , 28 (1): 84–89, arXiv : math/9301216 , doi :10.1090/S0273-0979-1993-00335-5, MR  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 , ISBN 978-3-540-10704-0.
  7. ^ Chudnovsky, Maria ; Robertson, Neil ; Seymour, Paul ; Thomas, Robin (2006), "El teorema del grafo perfecto fuerte" (PDF) , Anales de Matemáticas , 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 aristas", 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 grafos en serie-paralelos", 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", Actas de la Octava Conferencia del Sureste sobre Combinatoria, Teoría de Grafos y Computación (Universidad Estatal de Luisiana, Baton Rouge, La., 1977) , Congressus Numerantium, vol. XIX, Winnipeg: Utilitas Math., págs. 311–315, MR  0505860
  12. ^ Bodlaender, Hans L. (1998), "Un k -arboreto parcial de grafos con ancho de árbol acotado", 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), "Gráficos con un ancho de rama de tres como máximo", 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 grafos n -coloreables", Journal of Combinatorial Theory , Serie B, 16 (2): 191–193, doi : 10.1016/0095-8956(74)90063-X , MR  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, Yury; Tyshkevich, Regina (1997), "Gráficos en línea de hipergrafos lineales 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, MR  1459889
  17. ^ Jacobson, MS; Kézdy, Andre E.; Lehel, Jeno (1997), "Reconocimiento de gráficos de intersección de hipergrafos 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 hipergrafos k -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 wye-delta-wye", 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.