MO405 - Questão para a prova oral

Número: 075

Enunciado: Sobre coloração de grafos, qual afirmativa está correta?

a) O grafo de Petersen é 3-cromático e 3-crítico.

b) Se um grafo é 10-crítico podemos afirmar que seu grau mínimo é maior ou igual a 9.

c) Um ciclo com 255 vértices é 5-crítico.

d) Um grafo de intervalos que possui um número de clique (número máximo de vértices numa clique) igual a 180 possui número cromático igual a 90.

e) NDA

Ideia original de: Edgard H. Santos