| dc.creator | Alcón, Liliana Graciela | |
| dc.creator | Bonomo, Flavia | |
| dc.creator | Mazzoleni, María Pía | |
| dc.date | 2017-05-25 | |
| dc.date | 2022-02-09T17:53:05Z | |
| dc.date.accessioned | 2023-07-15T04:18:26Z | |
| dc.date.available | 2023-07-15T04:18:26Z | |
| dc.identifier | http://sedici.unlp.edu.ar/handle/10915/130780 | |
| dc.identifier | issn:0911-0119 | |
| dc.identifier | issn:1435-5914 | |
| dc.identifier.uri | https://repositorioslatinoamericanos.uchile.cl/handle/2250/7469043 | |
| dc.description | Weinvestigate graphs that can be represented as vertex intersections of horizontal and vertical paths in a grid, the so called B0-VPG graphs. Recognizing this class is an NP-complete problem. Although, there exists a polynomial time algorithm for recognizing chordal B0-VPG graphs. In this paper, we present a minimal forbidden induced subgraph characterization of B0-VPG graphs restricted to block graphs. As a byproduct, the proof of the main theorem provides an alternative certifying recognition and representation algorithm for B0-VPG graphs in the class of block graphs. | |
| dc.description | Departamento de Matemática | |
| dc.description | Universidad de Buenos Aires | |
| dc.description | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.format | application/pdf | |
| dc.format | 653-664 | |
| dc.language | en | |
| dc.rights | http://creativecommons.org/licenses/by-nc-sa/4.0/ | |
| dc.rights | Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) | |
| dc.subject | Matemática | |
| dc.subject | vertex intersection graphs | |
| dc.subject | paths on a grid | |
| dc.subject | forbidden induced subgraphs | |
| dc.subject | block graphs | |
| dc.title | Vertex intersection graphs of paths on a grid: characterization within block graphs | |
| dc.type | Articulo | |
| dc.type | Preprint | |
