On a joint technique for Hajós' and Gallai's Conjectures

• Fábio Botler UChile
• Maycon Sambinelli Unicamp
• Rafael S. Coelho IFNMG
• Orlando Lee Unicamp

DOI: https://doi.org/10.5753/etc.2017.3191

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 |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₃, K₅ e K₅ − 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.

Referências

Bonamy, M. and Perrett, T. (2016). Gallai’s path decomposition conjecture for graphs of small maximum degree. ArXiv e-prints.

Bondy, A. (2014). Beautiful conjectures in graph theory. European J. Combin., 37:4–23.

Botler, F. and Jiménez, A. (2017). On path decompositions of 2k-regular graphs. Discrete Mathematics, 340(6):1405 – 1411.

Fan, G. (2005). Path decompositions and Gallai’s conjecture. J. Combin. Theory Ser. B, 93(2):117–125.

Favaron, O. and Kouider, M. (1988). Path partitions and cycle partitions of Eulerian graphs of maximum degree 4. Studia Sci. Math. Hungar., 23(1-2):237–244.

Geng, X., Fang, M., and Li, D. (2015). Gallai’s conjecture for outerplanar graphs. Journal of Interdisciplinary Mathematics, 18(5):593–598.

Granville, A. and Moisiadis, A. (1987). On Hajós’ conjecture (minimum cycle-partitions of the edge-set of Eulerian graphs). Congr. Numer., 56:183–187. Sixteenth Manitoba conference on numerical mathematics and computing (Winnipeg, Man., 1986).

Jiménez, A. and Wakabayashi, Y. (2014). On path-cycle decompositions of triangle-free graphs. ArXiv e-prints.

Lovász, L. (1968). On covering of graphs. In Theory of Graphs (Proc. Colloq., Tihany, 1966), pages 231–236. Academic Press, New York.

Pyber, L. (1996). Covering the edges of a connected graph by paths. J. Combin. Theory Ser. B, 66(1):152–159.

Seyffarth, K. (1992). Hajós’ conjecture and small cycle double covers of planar graphs. Discrete Math., 101(1-3):291–306. Special volume to mark the centennial of Julius Petersen’s “Die Theorie der regulären Graphs”, Part II.