Sobre la clique coloración de los grafos [4,2,2]

Abstract

Un grafo de intersección por aristas de una familia de caminos en un árbol huesped es llamado grafo EPT. Cuando el grado máximo del árbol huesped es 4, decimos que el grafo es [4, 2, 2]. En este trabajo, consideramos el problema de clique coloración en grafos [4,2, 2]. Probamos que esta clase de grafos es 3-clique coloreable y damos ejemplos de grafos en esta clase que no son 2-clique coloreables. Además, estudiamos subclases de grafos en [4, 2,2] que tienen número clique cromático menor o igual a 2.