##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 325.05114

**Autor: ** Bollobás, Béla; Erdös, Paul

**Title: ** Alternating Hamiltonian cycles. (In English)

**Source: ** Israel J. Math. 23, 126-131 (1976).

**Review: ** For natural numbers n and d, let K_{n}(\Delta_{c} \leq d) denote a complete graph of order n whose edges are colored so that no vertex belongs to more than d edges of the same color, and where \Delta_{c} is the maximal degree in the subgraph formed by the edges of color c. D. E. Daykin proved that if d = 2 and n \geq 6, then every such graph contains an alternating hamiltonian cycle (i.e. a spanning cycle whose adjacent edges have different colors). The authors have extended this as follows. Theorem: If 69d < n, then every G = K_{n}(\Delta_{c} \leq d) contains an alternating hamiltonian cycle. In fact, it is stated that if 69d < n, then every G = K_{n}(\Delta_{c} \leq d) contains alternating cycles of length \ell for every \ell, 3 \leq \ell \leq n. An analogous result is obtained as follows. Let \chi_{v} denote the number of colors appearing among the edges containing the vertex v, and let K_{n}(\chi_{v} \geq \lambda) denote a complete graph of order n whose edges are colored so that each vertex is on at least \lambda edges of different color. Theorem: Every K_{n}(\chi_{v} \geq (7/8)n) contains an alternating hamiltonian cycle. Several related results and conjectures are also presented.

**Reviewer: ** S.F.Kapoor

**Classif.: ** * 05C35 Extremal problems (graph theory)

05C15 Chromatic theory of graphs and maps

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag