MO405 - Questão para a prova oral

MO405 - Questão para a prova oral


Número:

Enunciado: Um grafo G é perfeito se χ(H) = ω(H) para todo subgrafo induzido H de G. Sabendo disso,  analise as afirmações abaixo e assinale a alternativa correta.

I   - Grafos cordais são perfeitos.

II - Grafos bipartidos são perfeitos; o que não é válido para seus respectivos grafos linha.

III  - Grafos de intervalos são perfeitos.

IV  - Todo grafo perfeito possui uma imersão planar.

a) Apenas a afirmação IV está incorreta.
b) As afirmações I, II e IV estão corretas.
c) As afirmações II e IV estão incorretas.
d) Apenas a afirmação I está correta.
e) N.D.A.


Ideia original de: Leandro Teófilo