Coloración gráfica
En teoría de grafos , la coloración de grafos es un caso especial de etiquetado de grafos ; es una asignación de etiquetas tradicionalmente llamadas "colores" a elementos de un gráfico sujetos a ciertas restricciones. En su forma más simple, es una forma de colorear los vértices de un gráfico de modo que no haya dos vértices adyacentes del mismo color; esto se llama coloración de vértices . De manera similar, un color de borde asigna un color a cada borde para que no haya dos bordes adyacentes del mismo color, y un color de cara de un gráfico plano asigna un color a cada cara o región para que no haya dos caras que compartan un límite con el mismo color. el mismo color.
La coloración de vértices se utiliza a menudo para introducir problemas de coloración de gráficos, ya que otros problemas de coloración se pueden transformar en una instancia de coloración de vértices. Por ejemplo, una coloración de borde de un gráfico es solo una coloración de vértice de su gráfico lineal , y una coloración de cara de un gráfico plano es solo una coloración de vértice de su dual . Sin embargo, los problemas de coloración que no son de vértice a menudo se plantean y estudian tal cual. Esto es en parte pedagógico y en parte porque algunos problemas se estudian mejor en su forma sin vértice, como en el caso de la coloración de bordes.
La convención de usar colores se origina en colorear los países de un mapa , donde cada cara está literalmente coloreada. Esto se generalizó para colorear las caras de un gráfico incrustado en el plano. Por dualidad plana se convirtió en colorear los vértices, y de esta forma se generaliza a todos los gráficos. En las representaciones matemáticas y de computadora, es típico usar los primeros números enteros positivos o no negativos como los "colores". En general, se puede utilizar cualquier conjunto finito como "conjunto de colores". La naturaleza del problema de coloración depende de la cantidad de colores, pero no de cuáles son.
La coloración de gráficos disfruta de muchas aplicaciones prácticas, así como desafíos teóricos. Además de los tipos clásicos de problemas, también se pueden establecer diferentes limitaciones en el gráfico, o en la forma en que se asigna un color, o incluso en el color en sí. Incluso ha alcanzado popularidad entre el público en general en forma del popular rompecabezas numérico Sudoku . La coloración de gráficos sigue siendo un campo de investigación muy activo.
Los primeros resultados sobre la coloración de gráficos tratan casi exclusivamente de gráficos planos en forma de coloración de mapas . Mientras trataba de colorear un mapa de los condados de Inglaterra, Francis Guthrie postuló la conjetura de los cuatro colores , y señaló que cuatro colores eran suficientes para colorear el mapa de modo que ninguna región que compartiera un borde común recibiera el mismo color. El hermano de Guthrie pasó la pregunta a su profesor de matemáticas Augustus de Morgan en el University College , quien lo mencionó en una carta a William Hamilton en 1852. Arthur Cayley planteó el problema en una reunión de la London Mathematical Society.en 1879. El mismo año, Alfred Kempe publicó un artículo que pretendía establecer el resultado, y durante una década se consideró resuelto el problema de los cuatro colores. Por su logro, Kempe fue elegido miembro de la Royal Society y más tarde presidente de la London Mathematical Society. [1]
En 1890, Heawood señaló que el argumento de Kempe estaba equivocado. Sin embargo, en ese artículo demostró el teorema de los cinco colores , diciendo que cada mapa plano puede colorearse con no más de cinco colores, usando ideas de Kempe. En el siglo siguiente, se desarrollaron una gran cantidad de trabajo y teorías para reducir el número de colores a cuatro, hasta que el teorema de los cuatro colores fue finalmente probado en 1976 por Kenneth Appel y Wolfgang Haken . La prueba se remonta a las ideas de Heawood y Kempe y en gran medida ignora los desarrollos intermedios. [2] La prueba del teorema de los cuatro colores también es digna de mención por ser la primera prueba importante asistida por computadora.
