Artículo
A note on Helly-B1-EPG graphs
Fecha de publicación:
10/2021
Editorial:
Sociedad Brasilera de Matemàtica
Revista:
Matemática Contemporânea
ISSN:
0103-9059
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
Edge intersection graphs of paths on a grid (EPG graphs) aregraphs whose vertices can be represented as nontrivial paths on agrid such that two vertices are adjacent if and only if the corresponding paths share at least one edge of the grid. When the paths haveat most one change of direction (bend) these graphs are called B1-EPG graphs. In this paper, we delimit some subclasses of B1-EPGgraphs that admit a Helly-B1-EPG representation. It is known thatB1-EPG and Helly-B1-EPG are hereditary classes, so they can becharacterized by forbidden structures. In both cases, finding thewhole list of minimal forbidden induced subgraphs are challengingopen problems. Taking a step towards solving those problems, wedescribe a few structures at least one of which will necessarily bepresent in any B1-EPG graph that does not admit a Helly representation. In addition, we show that the well known families of Blockgraphs, Cactus and Line of Bipartite graphs are totally contained inthe class Helly-B1-EPG.
Archivos asociados
Licencia
Identificadores
Colecciones
Articulos(CCT - LA PLATA)
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - LA PLATA
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - LA PLATA
Citación
Alcón, Liliana Graciela; Mazzoleni, María Pía; Dias Dos Santos, Tanilson; A note on Helly-B1-EPG graphs; Sociedad Brasilera de Matemàtica; Matemática Contemporânea; 48; 10-2021; 22-30
Compartir
Altmétricas