MO405 - Questão para a prova oral

Número:

Enunciado: Considere um C₅ onde cada vértice representa  uma fofoqueira e uma aresta representa um canal de comunicação entre 2 fofoqueiras. Sobre o Problema da Fofoca neste grafo, não podemos afirmar que:

a) É possível diminuir o número mínimo de mensagens ao incluir um novo canal de comunicação (C₅ + e).

b) É possível diminuir o número mínimo de mensagens mantendo o número de canais de comunicação, apenas reorganizando-os de uma melhor forma (n(G) = n(C₅); e(G) = e(C₅)).

c) É possível aumentar o número mínimo de mensagens ao excluir um canal de comunicação (C₅ - e).

d) Se uma nova fofoqueira for incluída ao grupo e possuir um canal de comunicação com 3 outras fofoqueiras, o número mínimo de mensagens aumentará em 1.

e) NDA

MO405 - Questão para a prova oral

Número:

Enunciado: Seja G um grafo conexo com o polinômio cromático n⁴ -3n³ +2n² -n. Não podemos afirmar que:

a) G é perfeito.

b) G é planar e seu grafo dual é Euleriano.

c) G possui um matching perfeito.

d) G possui pelo menos um vértice de corte e uma aresta de corte.

e) NDA

MO405 - Questão para a prova oral

Número:

Enunciado: Seja G uma árvore e H um ciclo. Podemos afirmar que:

a) A composição de G e H resulta em um grafo perfeito.

b) Todo subgrafo próprio de H é perfeito.

c) Se incluirmos uma aresta em G, o grafo obtido será imperfeito.

d) Se incluirmos n/2 arestas em H (mantendo-o simples), o grafo obtido será perfeito.

e) NDA

MO405 - Questão para a prova oral

Número:

Enunciado: Em qual dos grafos abaixo a aplicação do downshifting a partir do vértice v₂ resolveria o problema da coloração de arestas com Δ(G)+1 cores? (Δ(G) é o grau máximo do grafo)

a)

b)

c)

d)

e) NDA

MO405 - Questão para a prova oral

Número:

Enunciado: Considere dois grafos G e H. Qual das afirmações abaixo é falsa?

a) Se H é um minor de G, então G contém uma subdivisão de H.

b) Se G contém uma subdivisão de H, então H é um minor de G.

c) Existem grafos planares que podem ser coloridos com até 2 cores.

d) Existem grafos não-planares que podem ser coloridos com até 2 cores.

e) NDA

MO405 - Questão para a prova oral

Número:

Enunciado: Considere dois grafos G e H, onde H=G-e (H é obtido pela remoção de uma aresta e de G). Qual das afirmações abaixo é falsa?

a) Se G é um ciclo, então H possui uma ordem de eliminação simplicial.

b) Se G é um K₅,então H é planar.

c) Se G é perfeito, então H é perfeito.

d) Se G é planar, então H é planar e o dual de H é G.e (contração da aresta e em G).

e) NDA

MO405 - Questão para a prova oral

Número:

Enunciado: Seja T_n,r  um grafo Turán com n vértices e r partições. Qual das implicações abaixo é falsa?

a) Se n < 2r, então T_n,r é color-critical.

b) Se movermos um vértice de uma partição para outra, o grafo deixa de ter o máximo de arestas entre os grafos simples r-partidos.

c) Se incluirmos uma aresta em T_n,r , mantendo-o simples, o número cromático do grafo aumenta.

d) Se r=2, então o grafo é livre de triângulos.

e) NDA