![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/0/03/Desargues_graph_3color_edge.svg/langpt-640px-Desargues_graph_3color_edge.svg.png&w=640&q=50)
Coloração de arestas
De Wikipedia, a enciclopédia encyclopedia
Em teoria dos grafos, uma coloração de arestas de um grafo é a atribuição de “cores” para as arestas de um grafo de forma que não haja duas arestas adjacentes tendo a mesma cor. Por exemplo, a figura à direita mostra uma coloração de arestas de um grafo com as cores vermelha, azul e verde. Coloração de arestas é um dos vários tipos de coloração de grafos.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/0/03/Desargues_graph_3color_edge.svg/320px-Desargues_graph_3color_edge.svg.png)
O Problema da coloração de arestas pergunta se é possível colorir um dado grafo usando no máximo n cores. O número mínimo exigido de cores para um grafo é chamado de índice cromático. Por exemplo, o grafo à direita pode ser colorido com três cores, mas não pode ser colorido por duas cores, e, portanto, tem o índice cromático três.