Departamento de Computación

Un triángulo está determinado por tres vértices y tres aristas que unen dichos vértices. La gráfica de intersección de triángulos es una gráfica definida a partir de un conjunto de triángulos abiertos (es decir triángulos que no incluyen su frontera), donde cada vértice representa a un triángulo del conjunto, y existe una arista entre dos vértices si y sólo si los triángulos correspondientes se intersectan. El conjunto de triángulos abiertos está determinado por un conjunto de n puntos en el plano en posición general. Una coloración de Grundy de los vértices de una gráfica consiste en que cada par de vértices adyacentes tenga color distinto, y además cada vértice sea adyacente con al menos un vértice de cada color más pequeño que el suyo. El problema que estudiamos en esta tesis es encontrar el máximo número k de colores para el cual la gráfica de intersección de triángulos tiene una coloración de Grundy usando k colores. A este valor lo denominamos como el número de Grundy de la gráfica de intersección de triángulos. En este trabajo de tesis, damos cotas para el número de Grundy de la gráfica de intersección de triángulos. Además del número de Grundy, estudiamos otros parámetros para la gráfica de intersección de triángulos: su grado máximo y el tamaño del conjunto con número máximo de triángulos que se intersectan dos a dos y cuya intersección total es vacía. Construimos un programa que realiza coloraciones de Grundy. Estas coloraciones nos ayudaron a obtener nuestras cotas inferiores. Mientras que, para obtener nuestras cotas superiores utilizamos técnicas de conteo.

Abstract

A triangle is a polygon with three edges and three vertices. The intersection graph of triangles, is a graph in which the set of vertices corresponds to a set of open triangles( i.e. triangles that don’t include its border), and there is an edge between two vertices if and only if the corresponding triangles intersect. The set of open triangles is determined by a set of n points in general position in the plane. A Grundy coloring of a graph G is a vertex coloring of G having the property that for every two colors i and j, i < j, every vertex colored j has a neighbor colored i. The maximum positive integer k for which a graph G has a Grundy k- coloring is called the Grundy number of G. We study the Grundy number of the intersection graph of triangles. In this thesis, we give upper and lower bounds for the Grundy number of the intersection graph of triangles. If the points are in in general position, we give upper and lower bounds for the maximum degree for the intersection graph of triangles. Moreover when the points are in convex position, we give a lower bound for the maximum set of triangles in which each two intersect but the intersection of all the triangles is empty. We develop a computer program to search for the Grundy number. This program helped us to obtain the lower bounds. To obtain the upper bounds we used combinatorial techniques.