Coloración de los grafos EPT

MARÍA PÍA MAZZOLENI; PABLO DE CARIA; MARÍA GUADALUPE PAYO VIDAL

La Plata

Jornada; PRIMERA JORNADA DE TESISTAS DOCTORALES DEL DEPARTAMENTO DE MATEMÁTICA Y EL CMaLP. 2023; 2023

En esta charla, se abordará el tema de los grafos de intersección por aristas en una familia de caminos en un árbol huésped, conocidos como grafos EPT (Edge-Intersection Paths Tree). Se consideraran los grafos EPT-estrella y los grafos [4, 2, 2] y [5, 2, 2].Se comenzará presentando la definición de los grafos EPT y su relaciòn con el número clique cromático, destacando que estos grafos tienen un número clique cromático no acotado, como se ha demostrado en estudios anteriores (Cerioli y Petito, 2008).En el caso de los grafos [4, 2, 2] y [5, 2, 2], se mostrará que la subclases de grafos EPT-estrella son 2-clique coloreables, excepto para el ciclo de longitud 5 (C5). Además, se sabe que las clases [h,2,2]-estrella, con h ≥ 6, no son 2-clique coloreables (Cerioli y Petito, 2008).Por otro lado, se explorar ́a la posibilidad de permitir que el árbol huésped sea diferente de una estrella. En este contexto, se mostrar ́a que la clase [4, 2, 2] es 3-clique coloreable y se presentarán ejemplos de grafos minimales en esta clase que no son 2-clique coloreables. Asimismo, se mostrará que la clase [5, 2, 2], sin restricciones en el árbol huésped, es 3-clique coloreable.En la segunda parte de la charla, nos centraremos en la coloración propia de los grafos EPT. Exploraremos el índice cromático (χ′) y el número cromático (χ) en diversas subclases de grafos EPT, analizando còmo estos valores estàn relacionados con los parámetros del grafo.Mostremos que si G es un grafo [h, 2, 2]-estrella, entonces χ′(G) ≤ 2h −1 y χ(G) ≤ ⌈ 3h−1/2⌉. Además, veremos que en los grafos EPT libres de {2K2, diamante}, χ(G) = ω(G) o G = C5, siendo ω(G) el número máximo de vértices en un subgrafo completo del grafo. Por ultimo, mostraremos que si G es un EPT-estrella, entonces χ(G) ≤ ω(G) + 1.En la parte final de la charla, compartiremos los avances m ́as recientes, los nuevos enfoques y los futuros lineamientos.