On Colorings of EPT Graphs

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

Bahía Blanca

Congreso; XVII Congreso Dr. Antonio Monteiro. 202; 2023

The edge-intersection graph of a family of paths on a host tree is called an EP T 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.First we study the problem of clique coloring EPT graphs on bounded degree trees and then we deal with the usual problem of proper coloring in the class of EPT graph. 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-cliquecolorable. 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.We find the chromatic index (denoted by χ′), chromatic number (denoted by χ) and bounds of them depending on graph parameters for some subclasses of EPT graph. We prove that if G is an [h, 2, 2]-star graph, then χ′(G) ≤ 2h − 1 and χ(G) ≤ ⌈ 3h−1/2⌉. Moreover, if G is a {2K2, diamond}-free graph,then χ(G) = ω(G) or G = C5, being ω(G) the maximum number of vertices of a complete subgraph of the graph. We also show that if G is an EPT-star, then χ(G) ≤ ω(G) + 1. We continue working on other subclasses of EPT graphs in order to find bounds for the chromatic number and chromaticindex.