Gallai's conjecture asserts that every connected graph on n vertices can be decomposed into at most $\frac{{n + 1}}{2}$ paths. The E-subgraph of a graph G, denoted by $ G_e $, is the subgraph induced by the vertices of even degree in G. A triangle pair is a graph consisting of two triangles with exactly one vertex in common. In this paper, it is proved that Gallai's conjecture is true for graphs G in which $ G_e $ contains no triangle pair and each block of $ G_e $ has maximum degree at most 3.
Geng-Hua Fan, Jian-Feng Hou, Chui-Xiang Zhou
. Gallai's Conjecture on Path Decompositions[J]. Journal of the Operations Research Society of China, 2023
, 11(3)
: 439
-449
.
DOI: 10.1007/s40305-022-00435-3
[1] Lovász, L.: On covering of graphs. In: Erdös, P., Katona, G. (eds.) Theory of Graphs, pp. 231–236. Academic Press, New York (1968)
[2] Donald, A.: An upper bound for the path number of a graph. J. Graph Theory 4(2), 189–201(1980)
[3] Dean, N., Kouider, M.: Gallai's conjecture for disconnected graphs. Discret. Math. 213(1–3), 43–54(2000)
[4] Yan, L.: On path decompositions of graphs. Ph.D. Thesis, Arizona State University (1998)
[5] Favaron, O., Kouider, M.: Path partitions and cycle partitions of Eulerian graphs of maximum degree 4. Studia Sci. Math. Hungar. 23(1–2), 237–244(1988)
[6] Botler, F., Jiménez, A.: On path decompositions of 2k-regular graphs. Discret. Math. 340(6), 1405–1411(2017)
[7] Bonamy, M., Perrett, T.J.: Gallai's path decomposition conjecture for graphs of small maximum degree. Discret. Math. 342(5), 1293–1299(2019)
[8] Botler, F., Jiménez, A., Sambinelli, M.: Gallai's path decomposition conjecture for triangle-free planar graphs. Discret. Math. 342(5), 1403–1414(2019)
[9] Pyber, L.: Covering the edges of a connected graph by paths. J. Combin. Theory Ser. B. 66(1), 152–159(1996)
[10] Fan, G.: Path decompositions and Gallai's conjecture. J. Combin. Theory Ser. B. 93(2), 117–125(2005)
[11] Botler, F., Sambinelli, M.: Towards Gallai's path decomposition conjecture. J. Graph Theory 97(1), 161–184(2021)
