MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número: 077

Enunciado: De acordo com as afirmações abaixo, e lembrando que o produto cartesiano G □ H de G e H é definido como:

V(G □ H) = V(G) × V(H), e

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

assinale a alternativa correta:

I. O produto cartesiano de grafos bipartidos é um grafo bipartido;
II. Se o produto cartesiano de G e Km tem um conjunto independente de tamanho k, então G tem um subgrafo induzido de ordem k com número cromático no máximo m;
III. Nenhum ciclo pode ser representado por um grafo de intervalos.

a) Somente I e II estão corretas;

b)  Somente I e III estão corretas; 

c) Somente I está correta;

d) Todas estão corretas;

e) NDA.

 Ideia original de: Rafael L. Gomes