Edge Intersection Graphs of Paths on a Triangular Grid

Vitor T. F. de Luca; María Pía Mazzoleni; Fabiano S. Oliveira; Tanilson D. Santos; Jayme L. Szwarcfiter

paper

Edge Intersection Graphs of Paths on a Triangular Grid

arXiv:2203.04250

Abstract

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.

19 pages, 12 figures