MO405 - Questão para a prova oral

Número:

Enunciado: Considerando list coloring, qual das alternativas é correta?



a) O "chromatic number" é sempre menor que o "list chromatic number".

b) Computar o "list chromatic number" é tão difícil quanto computar "chromatic number".

c) O valor do maior grau de um grafo qualquer é sempre menor que o "list chromatic number".

d) O "list chromatic number" de um grafo planar é sempre maior que o valor do maior grau + 1.

e) nda

MO405 - Questão para a prova oral

Número:

Enunciado: Considerando grafos simples, qual das alternativas é correta?



a) Toda árvore com no mínimo três vértices tem no mínimo 3 folhas.

b) Se um grafo é 2-conexo então o grafo obtido da subdivisão de todas as suas arestas também é 2-conexo.

c) O número cromatico de um grafo qualquer é sempre menor ou igual ao seu número de clique.

d) Todo grafo planar simples possui um vértice com grau máximo 3.

e) nda

MO405 - Questão para a prova oral

Número:

Enunciado: Considerando o grafo (parcialmente colorido) da figura a seguir, o vertice v a ser colorido e cadeias de Kempe (as quais fizeram o colega Heber levar um negativo), qual das alternativas é correta?



a) A cadeia formada pelo caminho 6-2-1 com as cores amarela e azul permite que v seja colorido com a cor azul alterando apenas a cor dos vértices da cadeia.

b) A cadeia formada pelo caminho 6-2-3-1 com as cores amarela e azul permite que v seja colorido com a cor azul alterando apenas a cor dos vértices da cadeia.

c) A cadeia formada pelo caminho 5-3-1 com as cores amarela e azul permite que v seja colorido com a cor amarela vermelha alterando apenas a cor dos vértices da cadeia.

d) A formação apenas de cadeias de kempe neste grafo não é suficiente para 4 colorir seus vértices.

e) nda

MO405 - Questão para a prova oral

Número:

Enunciado: Considerando as afirmações de I a III, qual das alternativas é correta?

I todo grafo cúbico planar 2-aresta-conexo é hamiltoniano.
II Todo grafo que possui uma coloração de Tait pode ser 4-aresta-colorido.
III Um snark não possui coloração de Tait.


a) Todas são verdadeiras.

b) Todas são falsas.

c) I e III são falsas.

d) III é verdadeira.

e) nda

MO405 - Questão para a prova oral

Número:

Enunciado: Considerando as informações I a IV, qual das alternativas é correta?

I qualquer subgrafo de um grafo planar é planar.
II qualquer subgrafo de um grafo não-planar é não-planar.
III qualquer grafo que contém um subgrafo planar também é planar.
IV qualquer grafo que contém um subgrafo não-planar também é não-planar.


a) I e III são verdadeiras.

b) II e IV são verdadeiras.

c) II e III são falsas.

d) I e IV são falsas.

e) nda

MO405 - Questão para prova oral

Número:

Enunciado: A respeito de grafos cordais, qual das alternativas a seguir é correta?


a) Todo grafo completo é cordal.

b) Todo grafo planar é cordal.

c) Todo grafo bipartido completo é cordal.

d) O grafo de Petersen é cordal.

e) nda

MO405 - Questão para prova oral (11° semana)

Número:

Enunciado: Considerando grafos simples com 8 vertices e número cromático 4, qual das alternativas a seguir é correta?


a) O grafo contendo estas características possui no máximo 24 arestas.

b) O grafo contendo estas características possui no máximo 48 arestas.

c) O grafo contendo estas características possui no máximo 32 arestas.

d) O grafo contendo estas características possui no máximo 16 arestas.

e) nda