MO405 - Questão para a prova oral
Enunciado: Sobre a coloração de vértices de grafos simples é incorreto afirmar que:
A. Toda árvore com dois ou mais vértices é 2-colorível.
B. Ao se remover uma aresta de Kn o número cromático do grafo resultante diminui uma unidade, portanto, Kn é n-crítico (n-critical).
C. O algoritmo guloso de coloração sempre encontra uma coloração ótima para ciclos de tamanho par, independentemente da ordem em que os vértices são percorridos.
D. Se um grafo com n vértices tem α = (1 + n - ω), então χ = ω.
E. NDA.
Ideia original de: Lucas
Nenhum comentário:
Postar um comentário