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's theorem''', namednomeado forem honra a [[Vadim G. Vizing]] whoque discoveredo itdescobriu inem 1964, dividesdivide todos allos graphsgrafos intoem 2 classes: '''ClassClasse 1''' graphsgrafos havetem χ′(''G'') = Δ(''G''); '''ClassClasse 2''' graphsgrafos havetem χ′(''G'') = Δ(''G'')+1).
# χ′(''G'') ≤ Δ(''G'') + μ(''G''), onde ''G'' é permitido ser um [[multigrafo]].
 
 
<!--
# χ&prime;(''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 χ&prime;(''G'') = Δ(''G''); '''Class 2''' graphs have χ&prime;(''G'') = Δ(''G'')+1).
# χ&prime;(''G'') ≤ Δ(''G'') + μ(''G''), where ''G'' is allowed to be a [[Glossary of graph theory|multigraph]].
# χ&prime;(''G'') ≤ (3/2)Δ(''G'') for any multigraph {{harv|Shannon|1949}}