Sobre la coordinación de los complementos de línea de árboles

SAFE, MARTÍN; SUÁREZ ALBANESI, ROCÍO BELÉN

Salta

Congreso; Reunión Anual de la Unión Matemática Argentina; 2023

Universidad Nacional de Salta

Los grafos coordinados 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 y las clases de los grafos libres de paw y de los libres simultáneamente de gem, 4-wheel y bull. 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 y que el reconocimiento de grafos coordinados es NP-duro en general.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.