Coloraciones Borel en gráficas

Abstract

The study of the theory of graphs began several years ago, with the study of the problem of the bridges of Königsberg realized by Euler. Then, in the middle of the nineteenth century, this study reappeared when mathematicians of the time wondered if it was possible to color every map with only four colors and so that two neighboring countries had different color. In the attempt to solve the problem of the four colors, new concepts were defined and advances were made in this theory. But from the beginning they concentrated on the study of finite graphs. The problem of the four colors was translated to a problem of colorations of the vertices of a graph and was until some years ago that could be solved. The study of colorations by vertices always made thinking about the degree of the vertices and the number of small cycles. Erdös then proved that two fixed natural dyads, there is a graph that has a minimum cycle greater than the first natural and chromatic number greater than the natural second. Erdös-Bruijn's theorem extended many of the known results on the chromatic number of finite graphs to infinite graphs. This is because the theorem says that it suffices to look at the finite subgraphs. But surely, like many results that depend on the controversial Axiom of Choice, it has not been taken enough by the mathematicians who are dedicated to the study of graphs. Problems of edge coloring were also addressed, but this turned out to be less interesting; Because it was classified in two large classes of graphs, which can be colored with Δ (G) colors and can not be with these colors but with Δ (G) + 1 colors, where Δ (G) is the maximum number of Neighbors of a vertex in G.

El estudio de la teoría de gráficas comenzó hace ya varios años, con el estudio del problema de los puentes de Königsberg realizado por Euler. Después, a mediados del siglo XIX, resurgió este estudio cuando los matemáticos de la época se preguntaron si se podía colorear todo mapa con solo cuatro colores y de manera tal que dos países vecinos tuvieran color distinto. En el intento por resolver el problema de los cuatro colores, se definieron nuevos conceptos y se hicieron avances en esta teoría. Pero desde sus inicios se concentraron en el estudio de gráficas finitas. El problema de los cuatro colores fue traducido a un problema de coloraciones de los vértices de un gráfica y fue hasta hace algunos años que se pudo resolver. El estudio de las coloraciones por vértices siempre se hacía pensando en el grado de los vértices y en la cantidad de ciclos pequeños. Después Erdös probó que dodos dos naturales fijos, existe una gráfica que tiene un ciclo mínimo mayor que el primer natural y número cromático mayor que el segundo natural. El teorema de Erdös-Bruijn extendió muchos de los resultados conocidos sobre el número cromático de gráficas finitas a gráficas infinitas. Esto porque el teorema dice que basta fijarse en las subgráficas finitas. Pero seguramente, al igual que muchos resultados que dependen del tan polémico Axioma de Elección, no se le ha tomado suficiente importancia por los matemáticos que se dedican al estudio de gráficas. También se abordaron problemas de coloraciones por aristas de una gráfica, pero esto resultó no ser tan interesante; porque se clasificó en dos grandes clases de gráficas, las que se pueden colorear con Δ(G) colores y las no se pueden con estos colores pero sí con Δ(G) + 1 colores, donde Δ(G) es el máximo número de vecinos de un vértice en G.