Clique coloring EPT graphs on bounded degree trees

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

Buenos Aires

Congreso; The Latin-Iberoamerican Conference on Operations Research (CLAIO 2022); 2022

Universidad de Buenos Aires

Un grafo de intersección por aristas de una familia de caminos en un árbol huésped es llamado grafo EPT. 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.