On a joint technique for Hajós' and Gallai's Conjectures - Botler, Fábio; Sambinelli, Maycon; Coelho, Rafael S.; Lee, Orlando (Anais do Encontro de Teoria da Computação (ETC), 2017)
Uma decomposição de um grafo G em caminhos (resp. circuitos) é um conjunto de caminhos (resp. circuitos) arestas-disjuntos de G que cobre o conjunto de arestas de G. Gallai (1966) conjecturou que todo grafo com n vértices admite uma decomposição em caminhos D tal que |D| ≤ [(n+1)/2], e Hajós (1968) conjecturou que todo grafo Euleriano com n vértices admite uma decomposição em circuitos D tal que |D| ≤ [(n − 1)/2]. Neste trabalho, nós provamos a Conjectura de Gallai para grafos série-paralelos, e para grafos com grau máximo 4. Além disso, nós mostramos que os únicos grafos nessas classes que não admitem uma decomposição D tal que |D| ≤ [n/2] são isomorfos a K 3 , K 5 e K 5 − e. A técnica desenvolvida aqui é também usada para apresentar uma nova prova de um resultado de Grainwille e Moisiadis (1987) que diz que grafos Eulerianos com grau máximo 4 satisfazem a Conjectura de Hajós.