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

Abstract

A path (resp. cycle) decomposition of a graph G is a set of edge-disjoint paths (resp. cycles) of G that covers the edge-set of G. Gallai (1966) conjectured that every graph on n vertices admits a path decomposition of size at most [(n + 1)/2], and Hajós (1968) conjectured that every Eulerian graph on n vertices admits a cycle decomposition of size at most [(n − 1)/2]. In this paper, we verify Gallai’s Conjecture for series–parallel graphs, and for graphs with maximum degree 4. Moreover, we show that the only graphs in these classes that do not admit a path decomposition of size at most [n/2] are isomorphic to K₃, K₅ or K₅ − e. The technique developed here is further used to present a new proof of a result of Granville and Moisiadis (1987) that states that Eulerian graphs with maximum degree 4 satisfy Hajós’ Conjecture.

References

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.