On a joint technique for Hajós' and Gallai's Conjectures
Resumo
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 jDj b(n + 1)=2c, e Hajós (1968) conjecturou que todo grafo Euleriano com n vértices admite uma decomposição em circuitos D tal que jDj b(n 1)=2c. 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 jDj bn=2c são isomorfos a K3; K5 e K5 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.
