Characterizations and clique coloring of edge intersection graphs on a triangular grid

Abstract

We introduce a new class of intersection graphs, the edge intersec-tion graphs of paths on a triangular grid, called EPGt graphs. Weshow similarities and differences from this new class to the well-knownclass of EPG graphs. A turn of a path at a grid point is calleda bend. An EPGt representation in which every path has at mostk bends is called a Bk-EPGt representation and the correspondinggraphs are called Bk-EPGt graphs. We provide examples of B2-EPGgraphs that are B1-EPGt. We characterize the representation of cliqueswith three vertices and chordless 4-cycles in B1-EPGt representations.We also prove that B1-EPGt graphs have Strong Helly number 3.Furthermore, we prove that B1-EPGt graphs are 7-clique colorable.