MO405 - Questão para a prova oral

Número:

Enunciado: Qual é o número cromático de arestas do produto cartesiano dos grafos Cn e Cm, χ'(Cn □ Cm), com n, m ≥ 3.

a) min{n, m}

b) n*m

c) 4

d) n + m

e) NDA

Ideia original de: Rafael de Oliveira Werneck

MO405 - Questão para a prova oral

Número:

Enunciado: Seja G um grafo com número de vértice n, número de arestas e e cintura g. Assinale a expressão que corresponde à fórmula do número máximo de arestas para que o grafo G seja planar.

a) (g - 1)(n - 2) / (g - 2) ≥ e

b) g(n - g) / 2(g - 2) ≥ e

c) g(n - 2) / (g - 2) ≥ e

d) (2g + 1)(n - 2) / (g - 2) ≥ e

e) NDA

Ideia original de: Rafael de Oliveira Werneck

MO405 - Questão para a prova oral

Número:

Enunciado: Dado as seguintes afirmações, assinale a incorreta.

a) Se um grafo plano G é bipartido, então seu grafo dual (G*) é euleriano.

b) Um grafo cordal possui uma ordenação simplicial.

c) O grafo dual de um grafo dual não é, necessariamente, o grafo original.

d) A soma  dos comprimentos das faces é igual ao número de arestas.

e) NDA

Ideia original de: Rafael de Oliveira Werneck

MO405 - Questão para a prova oral

Número:

Enunciado: Assinale a alternativa incorreta à respeito da construção de Mycielski.

a) O grafo a ser construído possui o dobro mais um vértices do que o grafo original.

b) Todos vértices criados formam um conjunto independente.

c) O número cromático do grafo original é menor do que o do grafo construído.

d) Os vértices duplicados do grafo original possuem a mesma coloração dos vértices originais.

e) NDA

Ideia original de: Rafael de Oliveira Werneck