Grafos dualmente cordales y sus relaciones con otras clases

Abstract

Desde fines de los años ochenta varias investigaciones independientes estudiaron ciertas características especiales de grafos que sirvieron para definir nuevas clases. Así surgieron los grafos con órdenes de máximas vecindades, o grafos HT, los grafos árbol-clique 1 y los árboles expandidos. Un examen más detallado arrojó la conclusión de que estas clases definen al mismo tipo de grafos, lo cual hizo necesario el desarrollo de un enfoque unificado. Esto a su vez implicaba la conveniencia de una denominación universal para referirse a los grafos arriba mencionados. Fue así que comenzó a ganar terreno el concepto de grafos dualmente cordales. La clase de los grafos cordales ha sido ampliamente investigada y resulta muy útil desde un punto de vista algorítmico. La definición más básica y conocida dice que un grafo es cordal si no posee ciclos de longitud mayor o igual que cuatro como subgrafos inducidos. Sin embargo, se conocen más caracterizaciones, muchas de ellas con su correlato para grafos dualmente cordales. Este último hecho hará más comprensible la elección del nombre. En este trabajo se incluirán varias caracterizaciones de los grafos dualmente cordales. Se tratará la dualidad existente entre grafos cordales y dualmente cordales, siendo propicio para ello, entre otras cosas, trabajar con hipergrafos.