Partitioning regular graphs into equicardinal linear forests (Q1174174)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Partitioning regular graphs into equicardinal linear forests |
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
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