Sesión Matemática DiscretaSobre la coordinación de los complementos de línea de árboles*
Rocío Belén Suárez Albanesi
Departamento de Matemática, UNS e INMABB, UNS-CONICET, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Los grafos coordinados [1] son aquellos en los cuales, para todo subgrafo inducido, coinciden el grado clique (que es el cardinal máximo de un conjunto de cliques maximales que comparten todas un mismo vértice) y el número clique-cromático (que es el mínimo número de colores necesario para pintar las cliques maximales de modo que dos cliques maximales con el mismo color no compartan vértices).
La clase de grafos coordinados es hereditaria, es decir, cerrada por subgrafos inducidos. Por lo tanto, admite una caracterización por subgrafos inducidos prohibidos minimales. Si bien no se conoce una descripción completa de la lista de subgrafos inducidos prohibidos minimales para la clase de los grafos coordinados, sí se han obtenido resultados parciales para aquellos grafos coordinados dentro de las clases de los grafos de línea y de los complementos de árboles [3] y las clases de los grafos libres de paw y de los libres simultáneamente de gem, 4-wheel y bull [2]. Cada una de estas caracterizaciones conduce a un algoritmo de tiempo polinomial (o incluso lineal) para el reconocimiento de los grafos coordinados dentro de cada una de estas clases. Sin embargo, se sabe que la clase de los grafos coordinados admite familias de grafos prohibidos minimales cuya cardinalidad crece exponencialmente con el número de vértices [4] y que el reconocimiento de grafos coordinados es NP-duro en general [5].
En este trabajo, buscamos caracterizar por subgrafos inducidos prohibidos minimales cuándo un complemento de un grafo de línea de un árbol $T$ es coordinado. Conjeturamos una caracterización por subgrafos inducidos prohibidos minimales y la demostramos para todos los árboles $T$ con diámetro a lo sumo 5. Más aún, demostramos que para probar que la conjetura es cierta, alcanza con demostrarla para los árboles cuyo diámetro es 6.
*Este trabajo fue financiado parcialmente por el subsidio PGI 24/L115 de la Universidad Nacional del Sur. M.D. Safe fue financiado parcialmente por el subsidio PIBAA 28720210101185CO del CONICET.
Trabajo en conjunto con: Martín D. Safe (Departamento de Matemática, UNS e INMABB, UNS-CONICET).
Referencias
[1] F. Bonomo, G. Durán, and M. Groshaus. Coordinated graphs and clique graphs of clique-Helly perfect graphs. Util. Math., 72:175-191, 2007.
[2] F. Bonomo, G. Durán, F. Soulignac, and G. Sueiro. Partial characterizations of clique-perfect and coordinated graphs: Superclasses of triangle-free graphs. Discrete Appl. Math., 157(17):3511-3518, 2009.
[3] F. Bonomo, G. Durán, F. Soulignac, and G. Sueiro. Partial characterizations of coordinated graphs: line graphs and complements of forests. Math. Oper. Res., 69(2):251–270, 2009.
[4] F. Soulignac and G. Sueiro. Exponential families of minimally non-coordinated graphs. Rev. Un. Mat. Argentina, 50(1):75–85, 2009.
[5] F. Soulignac and G. Sueiro. NP-hardness of the recognition of coordinated graphs. Ann. Oper. Res., 169(1):17–34, 2009.