Edge Intersection Graphs of Paths on a Triangular Grid
share
We introduce a new class of intersection graphs, the edge intersection graphs of paths on a triangular grid, called EPGt graphs. We show similarities and differences from this new class to the well-known class of EPG graphs. A turn of a path at a grid point is called a bend. An EPGt representation in which every path has at most k bends is called a B_k-EPGt representation and the corresponding graphs are called B_k-EPGt graphs. We provide examples of B_2-EPG graphs that are B_1-EPGt. We characterize the representation of cliques with three vertices and chordless 4-cycles in B_1-EPGt representations. We also prove that B_1-EPGt graphs have Strong Helly number 3. Furthermore, we prove that B_1-EPGt graphs are 7-clique colorable.
READ FULL TEXT