Departamento de Computación

Una gráfica representada en el plano con puntos como vértices y segmentos de recta como aristas, es denominada gráfica geométrica. En este trabajo dar una coloración propia a las aristas de una gráfica consiste en asignar a cada arista un color, de tal manera que dos aristas que inciden en un mismo vértice o se cruzan no tengan el mismo color¹. El problema central que estudiamos es el de hallar el mínimo número de colores necesarios para dar una coloración propia a una gráfica geométrica, a este valor lo denominamos índice cromático de la gráfica. En este trabajo damos una cota inferior y una cota superior para el índice cromático de gráficas bipartitas dibujadas sobre conjuntos de puntos en posición convexa. Para gráficas no bipartitas dibujadas sobre este mismo tipo de conjuntos, determinamos el valor exacto del índice cromático. Para gráficas determinadas por ciertos tipo de conjuntos de puntos clásicos en la literatura de geometría combinatoria (doble cadena convexa y doble círculo convexo) determinamos el valor exacto del índice cromático. Si consideramos la gráfica en la que dos aristas son disjuntas si inciden en un mismo vértice o se cruzan, entonces el problema de determinar el índice cromático es distinto. Para este tipo de gráficas dibujadas sobre puntos en posición general mejoramos la cota inferior y la cota superior para el índice cromático. Mediante búsquedas exhaustivas hallamos el valor exacto del índice cromático de todas las posibles gráficas geométricas de orden 3, 4, 5 y 6. Adicionalmente mejoramos la cota inferior para el índice cromático geométrico de gráficas de intersección de orden par. Palabras clave: Índice Cromático, Gráfica Geométrica, Coloración propia, Índice Cromático Geométrico. ¹Esta condición de cruce hace que este problema sea totalmente distinto al problema de coloración en gráficas (abstractas).

Abstract

A geometric graph is a graph draw in the plane, in such a way that the vertices correspond to a point set and the edges are represented by straight-line segments. A proper coloring is an assignment of colors to the edges of the graph so that no two incident or crossing edges have the same color ². We study the problem of finding, for a geometric graph G, the minimum number of di_erent colors required to give a proper coloring of G, we call this value chromatic index of G. In this work we give to the edges lower bounds and upper bound for the chromatic index of bipartite geometric graphs whose vertex set consists of points in convex position. For complete geometric graphs whose vertex set consists of points in convex position, we obtain the exact value of the chromatic index. Similarly, we obtain the exact value of the chromatic index for graphs with vertex set consisting of certain types of points sets well known in combinatorial geometry (convex chain and double circle). we consider the graph in which two edges are disjoint if and only if they are adjacent or they cross, for this type of graph we improve the lower and upper bound for the chromatic index. Computationally we _nd the exact value of the chromatic index for intersection graphs of order 3, 4, 5 and 6. We improve the lower bound of the geometric chromatic index for intersection graphs of even order. Keywords:Chromatic Index, Geometric Graph, Proper Coloring, Geometric Chromatic Index. ²Due to this condition this problem and the classic problem of coloring (abstract) graphs are different.