Coloração de arestas

Questões-guia:

1. Como emparceirar n equipes que estejam disputando um campeonato de todos contra todos?  Quantas rodadas são necessárias?
2. Defina os seguintes termos: k-aresta-coloração, coloração própria de arestas, grafo k-aresta-colorável, índice cromático.
3. Para grafos simples G, o que pode dizer sobre a relação entre o índice cromático χ'(G) e o grau máximo Δ(G)?
4. O que é um grafo "classe 1"?  E um grafo "classe 2"?
5. A que classe pertencem os grafos bipartidos?
6. Qual a relação entre χ'(G) e Δ(G) em grafos com arestas múltiplas?
7.  O que é um grafo overfull (transbordante?)  A que classe tais grafos pertencem?
8. O que diz o Teorema de Vizing e quais os elementos principais de sua prova?  Consulte, além do livro de West, adotado nesta disiplina, um paper interessante de Misra e Gries sobre o assunto, publicado em 1990.

Exercícios:

1. Exercício 7.1.1 do West, apenas χ'(G).
2. Calcule o número de 3-aresta-colorações próprias de K_3,3.
3. Mostre um grafo G e uma escolha de emparelhamentos máximos tais que o algoritmo a seguir NÃO forneça o índice cromático de G.