Edgepartitioning into paths
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
A conjecture of Erdös and Gallai [4], 1959.
Every connected graph on \(n\) vertices can be edgepartitioned 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 edgepartitioned into at most \( \lfloor n/2 \rfloor\) cycles and paths.
A closely related problem is the following conjecture of Hajos[6]:
Chung [3] proved that a connected graph on \( n\) vertices can be partitioned into at most \( \lceil n/2 \rceil\) edgedisjoint 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].
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), 405417.

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

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

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

5  A. J. W. Hilton. Canonical edgecolourings of locally finite graphs. Combinatorics 2 (1982), 3751.

6 
L. Lovász,
On covering of graphs, Theory of Graphs, Proc. Coll. Tihany, 1966
(P. Erdös and G. O. H. Katona, eds.), 231236, 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), 257268.

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