Artículo
On some special classes of contact B0-VPG graphs
Fecha de publicación:
02/2022
Editorial:
Elsevier Science
Revista:
Discrete Applied Mathematics
ISSN:
0166-218X
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
A graph G is a B0-VPG graph if one can associate a horizontal or vertical path on a rectangular grid with each vertex such that two vertices are adjacent if and only if the corresponding paths intersect in at least one grid-point. A graph G is a contact B0-VPG graph if it is a B0-VPG graph admitting a representation with no one-point paths, no two paths crossing, and no two paths sharing an edge of the grid. In this paper, we present a minimal forbidden induced subgraph characterisation of contact B0-VPG graphs within four special graph classes: chordal graphs, tree-cographs, P4-tidy graphs and P5-free graphs. Moreover, we present a polynomial-time algorithm for recognising chordal contact B0-VPG graphs.
Palabras clave:
CONTACT B0-VPG GRAPH
,
CHORDAL GRAPH
,
TREE-COGRAPH
,
P4-TIDY GRAPH
,
P5-FREE GRAPH
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
Articulos(ICC)
Articulos de INSTITUTO DE INVESTIGACION EN CIENCIAS DE LA COMPUTACION
Articulos de INSTITUTO DE INVESTIGACION EN CIENCIAS DE LA COMPUTACION
Citación
Bonomo, Flavia; Mazzoleni, María Pía; Rean, Mariano Leonardo; Ries, Bernard; On some special classes of contact B0-VPG graphs; Elsevier Science; Discrete Applied Mathematics; 308; 2-2022; 111-129
Compartir
Altmétricas
Items relacionados
Mostrando titulos relacionados por título, autor y tema.
-
Bonomo-Braberman, Flavia; Durán, Guillermo; Safe, Martin Dario ; Wagler, Annegret K. (Elsevier Science, 2020-07-15)
-
de Caria, Pablo Jesús ; Gutierrez, Marisa (Elsevier Science, 2016-09)
-
Bonomo, Flavia ; Duran, Guillermo Alfredo ; Safe, Martin Dario ; Wagler, Annegret Katrin (Discrete Mathematics and Theoretical Computer Science, 2014-03)