zbMATH — the first resource for mathematics

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.

05C15 Coloring of graphs and hypergraphs
05C38 Paths and cycles
Full Text: DOI
[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
[4] Bermond, J.C.; Fouquet, J.L.; Habib, M.; Péroche, B., On lineark, Discrete math., 52, 123-132, (1984) · Zbl 0556.05054
[5] Jackson, B.; Wormald, N.C., On the lineark, 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.