Edge-partitioning into paths

A conjecture of Erdös and Gallai [4], 1959.

Every connected graph on \(n\) vertices can be edge-partitioned into at most \(\lfloor (n+1)/2 \rfloor\) paths.

Erdös and Gallai[4] showed that a connected graph with minimum degree \( d\) and at least \( 2d+1\) vertices has a path of length at least \( 2d+1\). Lovász [6] showed that every graph on \( n\) vertices can be edge-partitioned into at most \( \lfloor n/2 \rfloor\) cycles and paths.

A closely related problem is the following conjecture of Hajos[6]:

Conjecture 1   Every graph \( G\) on \( n\) vertices with all degrees even can be decomposed into at most \( \lfloor n/2 \rfloor\) edge-disjoint cycles.

Chung [3] proved that a connected graph on \( n\) vertices can be partitioned into at most \( \lceil n/2 \rceil\) edge-disjoint trees. Pyber [8] showed that every connected graph on \( n\) vertices can be covered by at most \( n/2 +O(n^{3/4})\) paths.

A linear forest is a disjoint union of paths. The following related conjecture is due to Akiyama, Exoo, Harary[1] and Hilton[5].

Conjecture 2   A graph of maximum degree \( \Delta\) can be covered by \( \lceil \frac{\Delta+1}{2} \rceil\) linear forests.

It is easy to see that \( \lceil \frac{\Delta+1}{2} \rceil\) linear forests are necessary to cover a regular graph of degree \( \Delta\). Alon[2] proved that a graph of maximum degree \( \Delta\) can be covered by \( \Delta/2 + c \Delta^{2/3} ( \log \Delta)^{1/3} \) linear forests. In 1995, McDiarmid and Reed [7] proved that almost every graph with maximum degree \( \Delta\) can be covered by \( \lceil \Delta /2 \rceil\) linear forests.

Bibliography
1 J. Akiyama, G. Exoo and F. Harary. Covering and packing in graphs III, Cyclic acyclic invariants, Math. Slovaca 30 (1980), 405-417.

2 N. Alon, The linear arboricity of graphs. Israel J. Math. 62 (1988), 311-325.

3 F. R. K. Chung. On partitions of graphs into trees, Discrete Math. 23 (1978), 23-30.

4 P. Erdös and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar. 10 (1959), 337-356.

5 A. J. W. Hilton. Canonical edge-colourings of locally finite graphs. Combinatorics 2 (1982), 37-51.

6 L. Lovász, On covering of graphs, Theory of Graphs, Proc. Coll. Tihany, 1966 (P. Erdös and G. O. H. Katona, eds.), 231-236, Academic Press, New York, 1968.

7 C. McDiarmid, B. Reed. Almost every graph can be covered by \( \lceil (\Delta +1)/2 \rceil\) linear forests, Comb. Prob. Compl 4 (1995), 257-268.

8 L. Pyber, Covering the edges of a connected graph by paths, J. Comb. Theory Ser. B 66 (1996), 152-159.