Subir material

Suba sus trabajos a SEDICI, para mejorar notoriamente su visibilidad e impacto

 

Mostrar el registro sencillo del ítem

dc.date.accessioned 2021-09-23T19:06:01Z
dc.date.available 2021-09-23T19:06:01Z
dc.date.issued 2019
dc.identifier.uri http://sedici.unlp.edu.ar/handle/10915/125545
dc.description.abstract 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. en
dc.language en es
dc.subject contact B 0-VPG graph es
dc.subject chordal graph es
dc.subject tree-cograph es
dc.subject P4-tidy graph es
dc.subject P5-free graph es
dc.title On some special classes of contact B0-VPG graphs es
dc.type Articulo es
sedici.identifier.other arXiv:1807.07372 es
sedici.identifier.other doi:10.1016/j.dam.2019.10.008 es
sedici.identifier.issn 0166-218x es
sedici.creator.person Bonomo Braberman, Flavia es
sedici.creator.person Mazzoleni, María Pía es
sedici.creator.person Rean, Mariano Leonardo es
sedici.creator.person Ries, Bernard es
sedici.subject.materias Ciencias Exactas es
sedici.subject.materias Matemática es
sedici.description.fulltext true es
mods.originInfo.place Centro de Investigación de Matemática es
sedici.subtype Preprint es
sedici.rights.license Creative Commons Attribution 4.0 International (CC BY 4.0)
sedici.rights.uri http://creativecommons.org/licenses/by/4.0/
sedici.description.peerReview peer-review es
sedici.relation.journalTitle Discrete Applied Mathematics es


Descargar archivos

Thumbnail
Documento
Descargar archivo (897.4Kb) - PDF

Este ítem aparece en la(s) siguiente(s) colección(ones)

Creative Commons Attribution 4.0 International (CC BY 4.0) Excepto donde se diga explícitamente, este item se publica bajo la siguiente licencia Creative Commons Attribution 4.0 International (CC BY 4.0)