Resumen:
Un grafo circular es el grafo intersección de cuerdas en un círculo. Estos han sido introducidos por Even e Itai en los '70 y muy estudiados en la literatura. Existen diferentes caracterizaciones para esta clase de grafos. Una de ellas utiliza el concepto de complementaciones locales, y fue aportada por André Bouchet en 1994. En el presente trabajo, utilizamos la idea de esta caracterización para definir una nueva clase, que generalizan a los circulares, y a los cuales llamamos Grafos de Bouchet. Probamos que estos grafos también generalizan a los grafos de intervalos, con lo que son una generalización de la unión de ambas clases; encontramos, por medio del uso de la computadora, una caracterización por 33 subgrafos prohibidos de la nueva clase; y vemos que como consecuencia de esta caracterización se obtiene un reconocimiento polinomial. Por último, mostramos que existen 396 formulaciones diferentes para el teorema de caracterización de Bouchet para grafos circulares.
Citación:
---------- APA ----------
Czemerinski, Hernán. (2001). Grafos de Bouchet : una generalización de los grafos circulares. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000172_Czemerinski
---------- CHICAGO ----------
Czemerinski, Hernán. "Grafos de Bouchet : una generalización de los grafos circulares". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2001.https://hdl.handle.net/20.500.12110/seminario_nCOM000172_Czemerinski
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000172_Czemerinski.pdf
Distrubución geográfica
