Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5. (English) Zbl 0930.05043
Summary: We prove the conjecture made by J. C. Bermond, J. L. Fouquet, M. Habib and B. Péroche [Discrete Math. 52, 123-132 (1984; Zbl 0556.05054)] that every cubic graph has an edge-coloring as described in the title. The number 5 cannot be replaced by 4. \(\copyright\) Academic Press.
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] | Akiyama, J.; Chvátal, V., A short proof of the linear arboricity for cubic graphs, Bull. Liber. Arts Sci. NMS, 2 (1981) |
| [3] | R. E. L. Aldred, N. C. Wormald; R. E. L. Aldred, N. C. Wormald |
| [4] | Bermond, J. C.; Fouquet, J. L.; Habib, M.; Péroche, B., On linear \(k\), Discrete Math., 52, 123-132 (1984) · Zbl 0556.05054 |
| [5] | Jackson, B.; Wormald, N. C., On the linear \(k\), Discrete Math., 162, 293-297 (1996) · Zbl 0870.05036 |
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.
