MAE478, Teoria dos Grafos

2023/2, Seminários
Professora Márcia R. Cerioli, Instituto de Matemática - UFRJ

Cada aluno deve escolher exatamente um tema. Cada aluno escolhe o dia em que irá apresentar o seminário, com antecedência de 2 semanas, e dentro do período letivo. Ambas as escolhas são do tipo "quem se manifestar primeiro, leva."

Os temas são livres, desde que complementem diretamente algum dos assuntos vistos na disciplina. Na dúvida, ou melhor, sempre pergunte a professora se o teu tema está dentro do contexto e se você está com as referências adequadas.

A ideia é o seminário ter duração de 50 minutos. Tanto slides quanto material impresso podem ser gerados para facilitar a apresentação e ela caber no tempo. Sempre fazer a conexão do conteúdo estudado em sala, inclusive usando os conceitos e teoremas estudados na disciplina, para chegar ao ponto principal do assunto escolhido para o seminário. Propor dois exercícios para os colegas resolverem e entregarem na aula seguinte.

A nota no seminário consiste na qualidade do material produzido, na abordagem introdutória, na explicação e prova do resultado central do tema escolhido, no uso do vocabulário, na fluência no uso dos resultados clássicos e na aplicação em exemplos. Cumprir o tempo de no máximo 1 hora de duração e não menos de 40 minutos. E na participação em todos os seminários dos colegas.

Quem não escolher até 7 de novembro terá o dia e/ou tema, sorteado.

Formulário de avalição

Calendário em 2023/2:

Sugestões de Tópicos para os seminários:

Segue uma lista de temas e referências que podem ser usadas para desenvolver um seminário, não é necessário se ater a esta lista.
  1. H.-J. Lai, L. Xiong, H. Yan, and J. Yan, Every 3-connected claw-free Z8-free graph is hamiltonian, J Graph Theory 64(1) (2010), 1--11. (ou algum resultado similar, provado anteriormente)

  2. ...
Tópicos já escolhidos:

  1. A. Conrad, T. Hindrichs, H. Morsy e I. Wegener. (1994). Solution of the Knight's Hamiltonian Path Problem on Chessboards. Discrete Applied Mathematics. 50 (2) (1994), 125--134. doi:10.1016/0166-218X(92)00170-Q

  2. Enunciado, explicação, exemplos e prova do teorema de Erdos-Gallai de caracterização de sequências gráficas.

  3. Prova do Teorema de Brooks. Não usar a referência do livro texto.

  4. Enunciado e prova do Teorema de Tutte (emparelhamentos perfeitos) e do Teorema de Petersen. Tem várias fontes de referência, a do livro texto parece ok.

  5. Prova do Teorema de Kuratowski (deve ser com subdivisões).

  6. B. Andrásfai, P. Erdos e V. T. Sós. On the connection between chromatic number, maximal clique and minimal degree of a graph. Discrete Math., 8:205--218.

  7. Cohen-Addad V. et all. Steinberg's Conjecture is false (todo grafo planar sem ciclo de tamanho 4 ou 5 é 3-colorível). Journal of Graph Theory, Series B 122 (2017) 452-456.

  8. Hakimi, S.L., Schmeichel, E.F.: On the connectivity of maximal planar graphs. J. Graph Theory 2, 307--314 (1978)

  9. O.V. Borodin et all. Grafos planares sem ciclos de tamanho 4, 5, 6 e 7 são 3-coloríveis. Colorings of plane graphs: a survey. Discrete Math 313 (2013) 517--539.

  10. Sobre o problema da face-aresta coloração de grafos planares. O caso do grau máximo 3. Daniel P. Sanders e Yue Zhao, Discrete Mathematics 220 (2000) 279-281.

  11. Grafos periplanares: hamiltonianos, coloração de vértices e de arestas, e outras propriedades.

  12. J. Zaks. Non-hamiltonian simple planar graphs. Annals of Discrete Mathematics 12 (1982) 255-263.

  13. J. Zaks, Non-Hamiltonian non-Grinbergian graphs, Discrete Math. 17 (1977) 317- 321.

  14. V. Chavatal e P. Erdos. A note on hamiltonian circuits. Discrete Math 2 (1972) 111-113.
Página criada em 27 mai 09, 15 set 17, 3 dez 17 Última alteração em 30 out 23 por Márcia R. Cerioli