Coloração de arestas: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Linha 11:
O menor número de cores necessárias em uma (própria) coloração de arestas de um grafo ''G'' é o '''índice cromático''', ou ''número cromático de arestas'', χ′(''G''), também, por vezes, simbolizado <math>\chi_1(G)</math>. Um grafo é '''''k''-arestas-cromático''' se o seu índice cromático é exatamente ''k''. O índice cromático não deve ser confundido com o [[número cromático]] χ(''G'').
== 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
▲# χ′(''G'') = 1 if and only if ''G'' is a [[Matching (graph theory)|matching]].
# χ′(''G'') ≥ Δ(''G'').
▲<!--
# χ′(''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]].
| |||