##
**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 cr^{2} 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