1. Edge Intersection Graphs of Paths on a Triangular Grid
- Author
-
de Luca, Vitor T. F., Mazzoleni, María Pía, Oliveira, Fabiano S., Santos, Tanilson D., and Szwarcfiter, Jayme L.
- Subjects
Computer Science - Discrete Mathematics ,Computer Science - Data Structures and Algorithms ,05C85, 05C05 - 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., Comment: 19 pages, 12 figures
- Published
- 2022