Sobre los Grafos Arista Intersección de Caminos en una Grilla Triangular

MARÍA PÍA MAZZOLENI; VITOR DE LUCA; FABIANO OLIVEIRA; JAYME SZWARCFITER

Neuquén

Congreso; LXXI Reunión Anual de la Unión Matemática Argentina; 2022

Introducimos una nueva clase de grafos de intersección, los Grafos Arista Intersección de Caminos en una Grilla Triangular, llamados grafos EPGt. Comparamos esta nueva clase con la bien conocida clase de los grafos EPG. Un giro de un camino en un punto de la grilla es llamado un bend. Una representación EPGt en la cual todo camino tiene a lo sumo k bends es llamada una representación Bk-EPGt y los grafos correspondientes son llamados grafos Bk-EPGt. Caracterizamos la representación de los cliques con tres vértices y los 4-ciclos inducidos en representaciones B1-EPGt.Además, consideramos el problema de clique coloración, esto es, colorear los vértices de un grafo dado de modo que ningún clique (maximal) esté monocoloreado. En general, clique coloración puede ser un problema bien diferente del problema de coloración usual de vértices. La principal diferencia es que clique coloración no es una propiedad hereditaria, es decir, un grafo puede ser k-clique coloreable y tener un subgrafo inducido que no lo es. Otra diferencia es que aún los grafos que son 2-clique coloreables pueden tener cliques arbitrariamente grandes. Sin embargo, la clique coloración tiene algunas similitudes con la coloración usual de vértices. Por ejemplo, toda k-coloración es también una k-clique coloración. Más aún, si G es un grafo libre de triángulos, el número clique cromático y el número cromático de G coinciden. En este trabajo, probamos que los grafos B1-EPGt son 7-clique coloreables.