b'\n_START_ARTICLE_\nColoraci\xc3\xb3n de grafos\n_START_PARAGRAPH_\nEn Teor\xc3\xada de grafos, la coloraci\xc3\xb3n de grafos es un caso especial de etiquetado de grafos; es una asignaci\xc3\xb3n de etiquetas llamadas colores a elementos del grafo. De manera simple, una coloraci\xc3\xb3n de los v\xc3\xa9rtices de un grafo tal que ning\xc3\xban v\xc3\xa9rtice adyacente comparta el mismo color es llamado v\xc3\xa9rtice coloraci\xc3\xb3n. Similarmente, una arista coloraci\xc3\xb3n asigna colores a cada arista tal que aristas adyacentes no compartan el mismo color, y una coloraci\xc3\xb3n de caras de un grafo plano a la asignaci\xc3\xb3n de un color a cada cara o regi\xc3\xb3n tal que caras que compartan una frontera com\xc3\xban tengan colores diferentes._NEWLINE_El v\xc3\xa9rtice coloraci\xc3\xb3n es el punto de inicio de la coloraci\xc3\xb3n, y los otros problemas de coloreo pueden ser transformados a una versi\xc3\xb3n con v\xc3\xa9rtices. Por ejemplo, una arista coloraci\xc3\xb3n de un grafo es justamente una v\xc3\xa9rtice coloraci\xc3\xb3n del grafo l\xc3\xadnea respectivo, y una coloraci\xc3\xb3n de caras de un grafo plano es una v\xc3\xa9rtice coloraci\xc3\xb3n del grafo dual._NEWLINE_La convenci\xc3\xb3n de usar colores se origina de la coloraci\xc3\xb3n de pa\xc3\xadses de un mapa, donde cada cara es literalmente coloreada. Esto fue generalizado a la coloraci\xc3\xb3n de caras de grafos inmersos en el plano. En representaciones matem\xc3\xa1ticas y computacionales se utilizan t\xc3\xadpicamente enteros no negativos como colores. En general se puede usar un conjunto finito como conjunto de colores. La naturaleza del problema de coloraci\xc3\xb3n depende del n\xc3\xbamero de colores pero no sobre cuales son.\n_START_SECTION_\nHistoria\n_START_PARAGRAPH_\nLos primeros resultados sobre coloraci\xc3\xb3n de grafos trataban exclusivamente sobre grafos planares en forma de coloraci\xc3\xb3n de mapas. Mientras intentaba colorear un mapa de Inglaterra, Francis Guthrie postul\xc3\xb3 la conjetura de los 4 colores, notando que 4 colores son suficientes para colorear el mapa tal que regiones que comparten un borde com\xc3\xban no reciban el mismo color. El hermano de Guthrie pasa el problema a su profesor de matem\xc3\xa1ticas Augustus de Morgan en la universidad, mencionado en una carta a William Hamilton en 1852. Arthur Cayley env\xc3\xada el problema a la London Mathematical Society en 1879. algunos a\xc3\xb1os despu\xc3\xa9s, Alfred Kempe public\xc3\xb3 un paper que resolv\xc3\xada el problema y por una d\xc3\xa9cada el problema de los 4 colores se consider\xc3\xb3 resuelto. Por su contribuci\xc3\xb3n Kempe fue elegido Fellow de la Royal Society y posteriormente presidente de la London Mathematical Society._NEWLINE_En 1890, Heawood descubri\xc3\xb3 que el argumento de Kempe conten\xc3\xada un error, en ese paper \xc3\xa9l prob\xc3\xb3 el teorema de los 5 colores, diciendo que cada mapa plano puede ser coloreado con, a lo m\xc3\xa1s 5 colores, usando ideas de Kempe. En el siguiente siglo, nuevas teor\xc3\xadas fueron desarrolladas para reducir el n\xc3\xbamero de colores a cuatro, hasta que el teorema de los 4 colores fue finalmente probado en 1976 por Kenneth Appel y Wolfgang Haken. _NEWLINE_La coloraci\xc3\xb3n de grafos han sido estudiada como un problema algor\xc3\xadtmico desde 1970: el problema del n\xc3\xbamero crom\xc3\xa1tico es el problema 21 de Karp NP-completo de 1972, y aproximadamente al mismo tiempo varios algoritmos de tiempo exponencial fueron desarrollados basados en backtraking y en la eliminaci\xc3\xb3n y MALA ntracci\xc3\xb3n de Zykov (1949). Una de las mayores aplicaciones de la coloraci\xc3\xb3n de grafos es la asignaci\xc3\xb3n de registros en compiladores introducida en 1981.\n_START_SECTION_\nV\xc3\xa9rtice coloraci\xc3\xb3n\n_START_PARAGRAPH_\nLa v\xc3\xa9rtice coloraci\xc3\xb3n (o simplemente coloraci\xc3\xb3n) es la asignaci\xc3\xb3n de los v\xc3\xa9rtices de un grafo con colores tal que dos v\xc3\xa9rtices que compartan la misma arista tengan colores diferentes. Un grafo con bucles no puede ser coloreado, y solo se consideran grafos simples._NEWLINE_La terminolog\xc3\xada de usar colores para etiquetar v\xc3\xa9rtices proviene del problema de colorear mapas. Las etiquetas como rojo o azul son solamente utilizadas cuando el n\xc3\xbamero de colores es peque\xc3\xb1o, y normalmente los colores est\xc3\xa1n representados por los enteros {1, 2, 3, \xe2\x80\xa6}._NEWLINE_Una coloraci\xc3\xb3n que usa a lo m\xc3\xa1s k colores se llama k-coloraci\xc3\xb3n (propia). El menor n\xc3\xbamero de colores necesarios para colorear un grafo G se llama n\xc3\xbamero crom\xc3\xa1tico y se denota como \xcf\x87(G). Un grafo que puede ser asignada una k-coloraci\xc3\xb3n (propia) es k-coloreable y es k-crom\xc3\xa1tico si su n\xc3\xbamero crom\xc3\xa1tico es exactamente k. Un subconjunto de v\xc3\xa9rtices asignados con el mismo color se llama una clase de color. Cada clase forma un conjunto independiente. Esto es, una k-coloraci\xc3\xb3n es lo mismo que una partici\xc3\xb3n del conjunto de v\xc3\xa9rtices en k conjuntos independientes, y los t\xc3\xa9rminos k-partito y k-coloreable tienen el mismo significado.\n_START_SECTION_\nArista coloraci\xc3\xb3n\n_START_PARAGRAPH_\nUna arista coloraci\xc3\xb3n de un grafo, es una coloraci\xc3\xb3n de las aristas, denotada como la asignaci\xc3\xb3n de colores a aristas tal que aristas incidentes tengan un color distinto. Una arista coloraci\xc3\xb3n con k colores es llamada k-arista-coloraci\xc3\xb3n y es equivalente al problema de particionar el conjunto de aristas en k emparejamientos. El menor n\xc3\xbamero de colores necesarios para un arista coloraci\xc3\xb3n de un grafo G es el \xc3\xadndice crom\xc3\xa1tico o n\xc3\xbamero crom\xc3\xa1tico de aristas. Una coloraci\xc3\xb3n Tait es una 3-arista-coloraci\xc3\xb3n de un grafo c\xc3\xbabico. El teorema de los cuatro colores es equivalente a que cada grafo c\xc3\xbabico sin puentes admite una coloraci\xc3\xb3n Tait.\n_START_SECTION_\nTeor\xc3\xada de Ramsey\n_START_PARAGRAPH_\nUna importante clase de problemas de coloreado impropias es estudiada en teor\xc3\xada de Ramsey, en donde se asignan colores a las aristas del grafo, y no hay restricci\xc3\xb3n sobre los colores en aristas incidentes. Un ejemplo simple es el teorema de la amistad que nos dice que en toda 2-arista-coloraci\xc3\xb3n del grafo completo de seis v\xc3\xa9rtices habr\xc3\xa1 un tri\xc3\xa1ngulo monocrom\xc3\xa1tico; extrapolando se puede interpretar que de un grupo de seis personas siempre hay tres que se conocen mutuamente o tres que no se conocen mutuamente. La teor\xc3\xada de Ramsey estudia la generalizaci\xc3\xb3n de esta idea para encontrar regularidad en el aparente desorden, e identificar condiciones generales para la existencia de subgrafos monocrom\xc3\xa1ticos con alguna estructura dada.'