Título: Sobre a Conjectura de Gallai

Palestrante: Maycon Sambinelli (CMCC-UFABC)

Data e local: Quarta, 24 de agosto de 2022 às 16:00, Campus Santo André, Bloco A, sala S-204-0

Resumo: Uma decomposição em caminhos de um grafo G é uma coleção de caminhos {P_1, P_2, P_3, …, P_n} tal que {E(P_1), E(P_2), …, E(P_n)} é uma partição de E(G). O path number de um grafo G, denotado por pn(G), é a menor cardinalidade de uma partição em caminhos. Em resposta a um pergunta de Erdős, Gallai, em 1967, conjecturou que todo grafo conexo com n vértices admite uma decomposição em caminhos com cardinalidade no máximo ⌈n/2⌉. Nessa palestra, discutiremos o estado atual de desenvolvimento desse problema.