Coloração de arestas: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Etiqueta: Ligações internas removidas |
|||
Linha 13:
== Propriedades ==
Em seguida, façamos Δ(''G'') denotar o [[grau (teoria dos grafos)|grau máximo]]; e μ(''G''), a multiplicidade. Algumas propriedades de χ′(''G''):
# χ′(''G'') = 1 se e somente se ''G'' é um
# χ′(''G'') ≥ Δ(''G'').
# χ′(''G'') ≤ Δ(''G'') + 1. ('''Teorema de Vizing''', nomeado em honra a [[Vadim G. Vizing]] que o descobriu em 1964, divide todos os grafos em 2 classes: '''Classe 1''' grafos tem χ′(''G'') = Δ(''G''); '''Classe 2''' grafos tem χ′(''G'') = Δ(''G'')+1).
| |||