Sobre la Clique Coloración de los Grafos EPT en árbol huésped de grado acotado

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

Conferencia; XXI LATIN IBERO-AMERICAN CONFERENCE ON OPERATIONS RESEARCH; 2022

Un grafo de intersección por aristas de una familia de caminos en un árbol huésped es llamado grafoEPT. Si el árbol huésped es una estrella diremos que el grafo es EPT-estrella. Cuando el gradomáximo del árbol huésped es $h$, decimos que el grafo es $[h,2,2]$ (respect. $[h,2,2]$-estrella). Sesabe que los grafos EPT tienen número clique cromático no acotado (ver [1]). En este trabajo,consideramos el problema de clique coloración en grafos $[4,2,2]$ y $[5,2,2]$. Primero, probamosque las clases de grafos $[4,2,2]$-estrella y $[5,2,2]$-estrella (exceptuando en este caso a $C_5$)son ambas $2$-clique coloreables. Sin embargo, las clases $[h,2,2]$-estrella, con h≥ 6, no son $2$-clique coloreables porque, por ejemplo, el grafo $G_h$, cuya representación EPT-estrella es $฀P_h,S_h฀$,siendo $S_h$ una estrella de grado $h$ y $P_h$ el conjunto de todos los posibles caminosde dos aristas de $S_h$, no es $2$-clique coloreable (ver [1]). Pero sabemos que las clases $[h,2,2]$-estrella con h≤ 16 son $3$-clique coloreables. Por otro lado, si permitimos que el árbol huespedsea diferente de una estrella, probamos que la clase $[4,2,2]$ es $3$-clique coloreable y damosejemplos de grafos minimales en esta clase que no son $2$-clique coloreables. Además,demostramos que la clase $[5,2,2]$, sin restricciones en el árbol huésped, es 3-clique coloreable.[1] M. R. Cerioli and P. Petito, Clique coloring UE and UEH graphs, Electronic Notes in DiscreteMathematics. 30 (2008) 201--206.