MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número:

Enunciado: Sobre as afirmações abaixo, assinale a alternativa correta:

I   -  Uma k-coloração própria de um grafo k-cromático é uma coloração ótima.
II  -  Um grafo é 2-colorível apenas se o grafo for bipartido.
III -  Para todo grafo G, χ(G) ≥ ω(G) e χ(G) ≥ α(G)/n(G)
IV - Para todo grafo G, χ(G) - 1 ≤ ∆(G)


a)  Apenas as alternativasI e II estão corretas
b)  Apenas a alternativa II está incorreta
c)  Apenas as alternativas I, II e III estão corretas
d)  Apenas a alternativa III está incorreta
e) N.D.A

Ideia original de: Leandro Teófilo