Clique coloring EPT graphs on bounded degree trees

Abstract

The edge-intersection graph of a family of paths on a host tree is called an EPT graph. When the host tree has maximum degree h , we say that the graph is [ h , 2 , 2 ] . If the host tree also satisfies being a star, we have the corresponding classes of EPT-star and [ h , 2 , 2 ] -star graphs. In this paper, we prove that [ 4 , 2 , 2 ] -star graphs are 2 -clique colorable, we find other classes of EPT-star graphs that are also 2 -clique colorable, and we study the values of h such that the class [ h , 2 , 2 ] -star is 3 -clique colorable. If a graph belongs to [ 4 , 2 , 2 ] or [ 5 , 2 , 2 ] , we prove that it is 3 -clique colorable, even when the host tree is not a star. Moreover, we study some restrictions on the host trees to obtain subclasses that are 2 -clique colorable.