On the linear \(k\)-arboricity of cubic graphs. (English) Zbl 0870.05036
Summary: J. C. Bermond et al. [Discrete Math. 52, 123-132 (1984; Zbl 0556.05054)] conjectured that the edge set of a cubic graph \(G\) can be partitioned into two \(k\)-linear forests, that is to say two forests whose connected components are paths of length at most \(k\), for all \(k\geq 5\). We shall prove a weaker result that the statement is valid for all \(k\geq 18\).
MSC:
| 05C35 | Extremal problems in graph theory |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C38 | Paths and cycles |
Citations:
Zbl 0556.05054References:
| [1] | Akiyama, J.; Exoo, G.; Harary, F., Covering and packing in graphs II, cyclic and acyclic invariants, Math. Slovaca, 30, 405-417 (1980) · Zbl 0458.05050 |
| [2] | Bermond, J. C.; Fouquet, J. L.; Habib, M.; Péroche, B., On linear \(k\)-arboricity, Discrete Math., 52, 123-132 (1984) · Zbl 0556.05054 |
| [3] | D. Delamarre, J.L. Fouquet, H. Thuillier and B. Virot, Linear \(k\); D. Delamarre, J.L. Fouquet, H. Thuillier and B. Virot, Linear \(k\) |
| [4] | Edmonds, J., Paths, trees, and flowers, Can. J. Math., 17, 449-467 (1965) · Zbl 0132.20903 |
| [5] | Gallai, T., Kritische Graphen II, Magyar Tud. Akad. Mat. Kutató Int. Közl., 8, 373-395 (1963) · Zbl 0144.23204 |
| [6] | Gallai, T., Maximale Systeme unabhängiger Kanten, Magyar Tud. Akad. Mat. Kutató Int. Közl., 9, 401-403 (1964) · Zbl 0135.42001 |
| [7] | Habib, M.; Péroche, B., Some problems about linear arboricity, Discrete Math., 41, 219-220 (1982) · Zbl 0486.05053 |
| [8] | Harary, F., Covering and packing in graphs 1, Ann. New York Acad. Sci., 175, 198-205 (1970) · Zbl 0226.05119 |
| [9] | Petersen, J., Die Theorie der regulären Graphen, Acta Math., 15, 193-220 (1891) · JFM 23.0115.03 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
