Em teoria dos grafos e em algoritmos , colorir as arestas de um grafo consiste em atribuir uma cor a cada aresta , evitando que duas arestas com extremidade comum sejam da mesma cor.
A figura ao lado é um exemplo de coloração correta das bordas. Na verdade, é verificado que nenhum vértice é comum a duas arestas da mesma cor. Observe que aqui não seria possível colorir as bordas do gráfico com apenas duas cores.
Mencionada sem maiores precisões, a expressão “coloração das arestas de um grafo” designa o fato de atribuir a cada aresta uma cor, de modo que duas arestas adjacentes (ou seja, tendo uma extremidade comum) nunca tenham a mesma cor. (É uma noção dupla de colorir os vértices de um gráfico .)
O número mínimo de cores necessário para atingir a coloração das arestas de um gráfico G é denominado índice cromático de G ou número cromático das arestas de G e χ ′ ( G ) observado , ou às vezes χ 1 ( G ). Não deve ser confundido com o número cromático (de vértices) de G , observado χ ( G ).
Se Δ ( G ) é o grau máximo de G e μ ( G ) sua multiplicidade (o número máximo de arestas por par de vértices), então:
Como afirmado acima, χ ′ ( G ) é sempre igual a Δ ( G ) ou a Δ ( G ) + 1. Diz-se que G é da classe 1 no primeiro caso e da classe 2 no segundo.
Em 1981, Holyer provou que determinar se um gráfico simples pertence a uma ou outra dessas duas classes é um problema NP-completo . No entanto, para alguns casos especiais, existem regras para uma conclusão rápida.
Por exemplo, Vizing estabeleceu que um gráfico planar simples de grau máximo igual a 8 é sempre de classe 1, e conjecturou que era o mesmo para um grau máximo igual a 6 ou 7 (conhecemos gráficos planares simples de grau máximo 2 , 3, 4 ou 5 e classe 2). Sanders (en) e Zhao provaram o caso Δ ( G ) = 7 de sua conjectura.
Esta conjectura encontra aplicação na coloração total (en) .
Colorir as bordas de gráficos completos pode ser usado para programar um torneio completo com o menor número de rodadas possível, de modo que cada par de competidores compita um contra o outro em uma das rodadas. Nesta aplicação, os vértices do gráfico correspondem aos competidores do torneio, as arestas correspondem aos jogos e as cores das arestas correspondem às rodadas em que os jogos são disputados.
Outra aplicação pode ser o planejamento da fabricação de um conjunto de objetos com a restrição de que cada tarefa de fabricação deve ser realizada em uma máquina específica, evitando que qualquer outra tarefa que requeira a mesma máquina seja executada ao mesmo tempo. Se todas as tarefas têm a mesma duração, então este problema pode ser formalizado como coloração de um multigrafo bipartido, em que os vértices de um lado da bipartição representam os objetos a serem fabricados, os vértices do outro lado das bipartições representam a fabricação máquinas, as bordas representam as tarefas a serem realizadas e as cores representam os intervalos de tempo em que cada tarefa pode ser realizada.