Coloração de arestas: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Linha 28:
(Holyer, 1981<ref>{{citar jornal|autor=HOLYER, Ian|ano=1981|título=The NP-completeness of edge-coloring|jornal=SIAM Journal on Computing|volume=10|páginas=718–720|doi=10.1137/0210055}}</ref>) provou que é [[NP-completo|'''NP'''-completo]] determinar se um grafo simples é Classe 1 ou Classe 2.
No entanto, esforços têm sido feitos para dar uma caracterização parcial.
Por exemplo, Vizing (1965)<ref>{{citar jornal|autor=VIZING, V. G. | ano = 1965 | título=Critical graphs with given chromatic class|jornal= Metody Diskret. Analiz.|volume=5|páginas=9–17|idioma=russo}}.</ref> mostrou que um grafo simples planar é da Classe 1, se o seu grau máximo é de pelo menos 8.
<!--
Linha 83 ⟶ 85:
| title = On an estimate of the chromatic class of a ''p''-graph | id = {{MR|0180505}}
| journal = Diskret. Analiz. | volume = 3 | pages = 25–30}}.
==External links==
| |||