Edge Intersection Graphs of Paths on a Triangular Grid

March 08, 2022 ยท The Ethereal ยท ๐Ÿ› Anais do VII Encontro de Teoria da Computaรงรฃo (ETC 2022)

๐Ÿ”ฎ THE ETHEREAL: The Ethereal
Pure theory โ€” exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Vitor T. F. de Luca, Marรญa Pรญa Mazzoleni, Fabiano S. Oliveira, Tanilson D. Santos, Jayme L. Szwarcfiter arXiv ID 2203.04250 Category cs.DM: Discrete Mathematics Cross-listed cs.DS Citations 1 Venue Anais do VII Encontro de Teoria da Computaรงรฃo (ETC 2022) Last Checked 5 months ago
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.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

๐Ÿ“œ Similar Papers

In the same crypt โ€” Discrete Mathematics