MO640 - Questão para a prova oral

Número: 013

Enunciado:
Sobre os grafos de intervalos, é correto afirmar:

1. Não é conhecido um algoritmo que determine, em tempo polinomial no tamanho do grafo, se um grafo é de intervalos.
2. Todo subgrafo induzido de um grafo de intervalos é de intervalos.
3. Se um subgrafo induzido de um grafo é de intervalos, o grafo original também é de intervalos.
4. O grafo C₄ (ciclo de 4 vértices) pertence a essa classe.
5. NDA

Autor(a): Marília Felippe Chiozo