Coloração de arestas: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Linha 15:
# χ′(''G'') = 1 se e somente se ''G'' é um [[Acoplamento (teoria dos grafos)|acoplamento]].
# χ′(''G'') ≥ Δ(''G'').
# χ′(''G'') ≤ Δ(''G'') + 1. ('''Teorema de Vizing
# χ′(''G'') ≤ Δ(''G'') + μ(''G''), onde ''G'' é permitido ser um [[multigrafo]].
<!--
▲# χ′(''G'') ≤ Δ(''G'') + 1. ('''Vizing's theorem''', named for [[Vadim G. Vizing]] who discovered it in 1964, divides all graphs into 2 classes: '''Class 1''' graphs have χ′(''G'') = Δ(''G''); '''Class 2''' graphs have χ′(''G'') = Δ(''G'')+1).
# χ′(''G'') ≤ Δ(''G'') + μ(''G''), where ''G'' is allowed to be a [[Glossary of graph theory|multigraph]].
# χ′(''G'') ≤ (3/2)Δ(''G'') for any multigraph {{harv|Shannon|1949}}
|