Coloraciones de aristas con restricciones en subgrafos

Abstract

En esta tesis se estudian tres tipos de coloraciones de aristas de grafos. En el primer capítulo, la introducción, damos una breve historia de las coloraciones de grafos. Luego hacemos una descripción de coloraciones de aristas en las que dos colores cualesquiera de la misma forman un ciclo hamiltoniano, coloraciones perfectas, o coloraciones acíclicas, donde dos colores forman un subgrafo acíclico. También introducirnos un nuevo tipo de coloración, que hemos llamado coloración aritmética de aritstas. En cada caso se describen los resultados existentes y los que se han obtcnido en esta tesis. En el segundo capítulo nos concentramos en los resultados que obtuvimos en coloraciones perfectas. Estos corresponden a un análisis de la cantidad de pares perfectos, pares de colores que inducen un ciclo hamiltoniano, que puede tener una coloración del grafo bipartito balanceado completo con 2n vórtices, dando el valor exacto en el caso de que n sea pal y una cota inferior si n cs impar. En el tercer capítulo utilizamos resultados del capítulo 2 para construir una coloración acíclica del grafo bipartito completo balanceado con 2n vértices, usando 2n * 4 colores, para n un número primo impar, En el último capítulo, se define la noción de coloración aritmética y se demuestran diferentes cotas superiores e inferiores para la cantidad mínima de colores necesaria para obtenerla, en términos de parámetros como el grado máximo del grafo y el número cromático inyectivo, También se presentan resultados sobre la complejidad computacional del cálculo de una coloración aritmética óptima, i.e. el cálculo del índice aritmético. En el apéndice damos algunas definiciones básicas de Teoría de Grafos.

In this thesis three types of edge colorings of graphs are studied. In the first chapter, the introduction, we give a brief history of graph colorings. Then we make a description of edgc colorings in which any two colors form a special subgraph. An edge coloring is a perfect coloring when the subgraph that these colors determine is a Hamiltonian cycle, while it is an acyclic coloring when this subgraph is acyclic. We also introduce a new type of edge coloring, which we call, arithmetic colort'ng. In each case the previous results and those obtained iu this thesis are described. In the second chaptcr we focus on results we have obtained about perfect colorings in balanced complete bipartite graphs. These correspond to a quantitative analysis of the mrmber of pairs of colors inducing a Hamiltonian cyc1e. When the graph has 2n vertices, we determine the exact value if n is even, and a lower bound if n is odd. In the third chapter we use results of Chapter 2 to construct an acyclic coloring of the corrplete bipartite balanced graph with 2n vertices, using 2n * 4 colors, when n is an odd prime number. In the last chapter, the notion of arithmetic coloring is defined. We obtain upper and lower bounds for the minimum number of colors required to obtain an optimal arithmetic coloring. These bounds are given in terms of the maximum degree of the graph and the injective chromatic number. We also present some results on the computational complexity of computing an optimal arithmetic coloring. In the appendix we give some basic definitions of Graph Theory.