Partitioning regular graphs into equicardinal linear forests (Q1174174)

From MaRDI portal





scientific article; zbMATH DE number 8202
Language Label Description Also known as
English
Partitioning regular graphs into equicardinal linear forests
scientific article; zbMATH DE number 8202

    Statements

    Partitioning regular graphs into equicardinal linear forests (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    25 June 1992
    0 references
    \textit{J. Akiyama, G. Exoo} and \textit{F. Harary} [Math. Slovaca 30, 405--417 (1980; Zbl 0458.05050)] showed that every 3-regular graph has a partition of the edge set into two linear forests. They [Networks 11, 69--72 (1981; Zbl 0479.05027)] also showed that the edge set of a 4-regular graph can be partitioned into three linear forests. The authors show that these results hold even when the forests all are required to have the same edge cardinality (assuming the original edge cardinality satisfies an obvious necessary congruence). The conjecture by the first author, \textit{C. Colbourn} and \textit{D. Holton} [Problem 13, Ars Comb. 23A, 332--334 (1987)] that the edge set of a 3-regular graph with an even number of edges can be partitioned into two isomorphic linear forests remains open.
    0 references
    regular graph
    0 references
    linear forests
    0 references

    Identifiers