Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 766.05062
Autor: Erdös, Paul; Gyárfás, A.; Pyber, L.
Title: Vertex coverings by monochromatic cycles and trees. (In English)
Source: J. Comb. Theory, Ser. B 51, No.1, 90-95 (1991).
Review: A. Gyárfás [Irregularities of partitions, Pap. Meet., Fertod/Hung. 1986, Algorithms Comb. 8, 89-91 (1989; Zbl 736.05062)] conjectured that if the edges of a complete graph K are colored with r colors then, for some function f, the vertex set of K can be covered by at most f(r) vertex disjoint monochromatic paths. Allowing cycles to include single vertices and edges, the authors prove a stronger form of the conjecture: If the edges of a complete graph K are colored with r colors then the vertex set of K can be covered by at most cr2 log r vertex disjoint monochromatic cycles. This result makes it possible to define, as a function of r, the minimum number of monochromatic cycles (or paths or trees) needed to cover (or partition) the vertex set of any r-colored complete graph. The authors conjecture that the cycle partition number is r and that the tree partition number is r-1 and prove these for the case r = 3.
Reviewer: R.C.Entringer (Albuquerque)
Classif.: * 05C70 Factorization, etc.
05C38 Paths and cycles
05C05 Trees
05C15 Chromatic theory of graphs and maps
Keywords: vertex coverings; complete graph; monochromatic paths; monochromatic cycles; paths; trees; cycle partition number; tree partition number
Citations: Zbl 736.05062
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag