Sobre los grafos PVPG: una subclase de los grafos vértice intersección de caminos en una grilla

LILIANA ALCÓN; FLAVIA BONOMO; MARÍA PÍA MAZZOLENI; FABIANO OLIVEIRA

Rio de Janeiro

Workshop; VIII Latin-American Workshop on Cliques in Graphs -LAWCliques'2018; 2018

Los grafos vértice intersección de caminos en una grilla (grafos VPG) songrafos cuyos vértices pueden ser representados como caminos en una grillatal que dos vértices son adyacentes si y sólo si los caminos correspondientescomparten al menos un vértice de la grilla. Se sabe que reconocer a los grafosVPG es un problema NP-completo. En este trabajo, estudiamos la clase delos grafos PVPG, esta es una subclase de los grafos VPG tal que todos loscaminos representantes están entre dos rectas paralelas y tienen sus puntosfinales sobre estas rectas. Probamos que PVPG = Co-comparabilidad. Másaún, presentamos algunos subgrafos inducidos prohibidos minimales para laclase de los grafos B1-PVPG (esto es, grafos PVPG donde cada camino tienea lo sumo un bend).