UMA 2022
Introducimos una nueva clase de grafos de intersección, los Grafos Arista Intersección de Caminos en una Grilla Triangular, llamados grafos EPG$_{t}$. 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 EPG$_{t}$ en la cual todo camino tiene a lo sumo $k$ bends es llamada una representación B$_k$-EPG$_{t}$ y los grafos correspondientes son llamados grafos B$_k$-EPG$_{t}$. Caracterizamos la representación de los cliques con tres vértices y los $4$-ciclos inducidos en representaciones B$_{1}$-EPG$_{t}$.
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 B$_{1}$-EPG$_{t}$ son $7$-clique coloreables.
Trabajo en conjunto con: Vitor Tocci F. de Luca (Universidade do Estado do Rio de Janeiro, Brasil), Fabiano S. Oliveira (Universidade do Estado do Rio de Janeiro, Brasil) y Jayme Szwarcfiter (Universidade Federal do Rio de Janeiro, Brasil).