MO405 - Questão para a prova oral

Número: 070

Enunciado: Lembrando que:

V(G □ H) = V(G) × V(H), e
E(G □ H) = {(u,v)(u',v') | (u ∈ V(G) e vv' ∈ E(H)) ou (uu' ∈ E(G) e v ∈ V(H))}

V(G ∨ H) = V(G) ∪ V(H), sendo V(G) e V(H) disjuntos, e
E(G ∨ H) = E(G) ∪ E(H)

O que podemos dizer sobre as afirmações a seguir ?

I - Todo grafo G completo com n(G) > 1 é crítico (color-critical)
II - O número cromático de G □ H é X(G) + X(H)
III - O número cromático de G ∨ H é max{X(G), X(H)}

a) Apenas II e III estão corretas
b) Apenas II está correta
c) Apenas I está correta
d) As três afirmações estão corretas
e) NDA

Ideia original de: Vitor Afonso