Coloración de Grafos
La coloración de grafos asigna etiquetas, o colores, a los elementos de un grafo de modo que los elementos adyacentes difieran, y estudia el número mínimo de colores requeridos.
Definition
Una coloración propia de un grafo es una asignación de colores a sus vértices de modo que no haya dos vértices adyacentes que compartan el mismo color; el número cromático es el menor número de colores para el cual existe tal asignación.
Scope
Este tema aborda la coloración propia de vértices y el número cromático, la coloración de aristas y el índice cromático, el polinomio cromático que cuenta las coloraciones, y resultados clave como el teorema de Brooks, el teorema de Vizing y el Teorema de los Cuatro Colores para grafos planares. Vincula la coloración con la independencia, las cliques y la teoría más amplia de los parámetros de grafos.
Core questions
- ¿Cuál es el menor número de colores necesarios para colorear correctamente un grafo dado?
- ¿Cuántas coloraciones propias con una paleta dada admite un grafo?
- ¿Qué grafos se pueden colorear con pocos colores y qué obstrucciones fuerzan muchos?
- ¿Cómo extienden las coloraciones de aristas y las coloraciones de listas la noción básica?
Key concepts
- Coloración propia de vértices
- Número cromático
- Polinomio cromático
- Coloración de aristas e índice cromático
- Teorema de Brooks
- Teorema de los Cuatro Colores
Key theories
- Teorema de los Cuatro Colores
- Todo grafo planar puede colorearse correctamente con un máximo de cuatro colores, una afirmación abierta durante más de un siglo y probada por primera vez por Appel y Haken en 1976 utilizando un extenso análisis de casos asistido por computadora.
- Teorema de Vizing
- Las aristas de cualquier grafo simple pueden colorearse correctamente con el grado máximo o con un color más que el grado máximo, dividiendo todos los grafos en dos clases estrechas.
Clinical relevance
La coloración modela la asignación de recursos sin conflictos: la programación sin colisiones, la asignación de registros en compiladores, la asignación de frecuencias en redes inalámbricas y los problemas de restricciones tipo Sudoku se reducen a la coloración de grafos.
History
La Conjetura de los Cuatro Colores, planteada en 1852, impulsó gran parte de la teoría de la coloración; su prueba asistida por computadora en 1976 por Appel y Haken fue un hito temprano en las matemáticas asistidas por computadora y generó debate sobre la naturaleza de la prueba.
Debates
- Estado de las pruebas asistidas por computadora
- La dependencia del Teorema de los Cuatro Colores de casos verificados por máquina planteó la cuestión de si una prueba demasiado larga para que un humano la verificara a mano debería considerarse una prueba matemática genuina.
Key figures
- Kenneth Appel
- Wolfgang Haken
- Vadim Vizing
Related topics
Seminal works
- diestel2017
Frequently asked questions
- ¿Qué es el número cromático de un grafo?
- Es el número más pequeño de colores necesarios para que los vértices adyacentes siempre reciban colores diferentes; por ejemplo, un ciclo impar tiene un número cromático de tres.
- ¿El Teorema de los Cuatro Colores se aplica a todos los mapas?
- Se aplica a mapas dibujados en el plano o la esfera donde las regiones están conectadas; los mapas en superficies como el toro pueden requerir más colores.