Sesión Matemática Discreta

Diciembre 13, 11:00 ~ 11:20

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

Mazzoleni, Maria Pia

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

Autores: Mazzoleni, Maria Pia / Alcón, Liliana / Bonomo, Flavia.