Sesión Matemática Discreta y Teoría de JuegosSobre la Clique Coloración de los Grafos EPT en árbol huésped de grado acotado
María Pía Mazzoleni
Universidad Nacional de La Plata, Facultad de Ciencias Exactas, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
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 grado máximo del árbol huésped es \(h\), decimos que el grafo es \([h,2,2]\) (respect. \([h,2,2]\)-estrella). Se sabe 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, probamos que 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\geq 6\), no son \(2\)-clique coloreables porque, por ejemplo, el grafo \(G_h\), cuya representación EPT-estrella es \(\langle P_h, S_h\rangle\), siendo \(S_h\) una estrella de grado \(h\) y \(P_h\) el conjunto de todos los posibles caminos de dos aristas de \(S_h\), no es \(2\)-clique coloreable (ver [1]). Pero sabemos que las clases \([h,2,2]\)-estrella con \(h\leq 16\) son \(3\)-clique coloreables. Por otro lado, si permitimos que el árbol huésped sea diferente de una estrella, probamos que la clase \([4,2,2]\) es \(3\)-clique coloreable y damos ejemplos 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.
Trabajo en conjunto con: Pablo Jesús De Caria Di Fonzo (Universidad Nacional de La Plata, Argentina) y María Guadalupe Payo Vidal (Universidad Nacional de La Plata, Argentina).
Referencias
[1] M. R. Cerioli and P. Petito, Clique coloring UE and UEH graphs, Electronic Notes in Discrete Mathematics. 30 (2008) 201-206.