Coloring EPT graphs on bounded degree trees

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

REVISTA DE LA UNIóN MATEMáTICA ARGENTINA

UNION MATEMATICA ARGENTINA

Lugar: Bahia Blanca; Año: 2023

0041-6932

The edge-intersection graph of a family of paths on a host tree iscalled 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 discuss about the values of h such that the class [h,2,2]-star is 3-clique colorable. If G belongs to [4,2,2] or [5,2,2] we prove that G 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.