##
**Zentralblatt MATH**

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

**Zbl.No: ** 316.05111

**Autor: ** Erdös, Paul; Simonovits, M.; Sos, V.T.

**Title: ** Anti-Ramsey theorems. (In English)

**Source: ** Infinite finite Sets, Colloq. Honour Paul Erdös, Keszthely 1973, Colloq. Math. Soc. Janos Bolyai 10, 633-643 (1975).

**Review: ** [For the entire collection see Zbl 293.00009.]

Let H be a fixed graph: f(n; H) denotes the maximum number so that any edge coloring of K^{n}, the complete graph on n vertices, which uses f(n; H) or more distinct colors yields a subgraph isomorphic with H each edge of which has a different color (a totally multicolored subgraph). The paper contains a reformulation of some earlier results, some new results, and some conjectures, all concerning the function f(n,H). For example: Theorem 4 (a new result): Let p \geq 4. There exists an n_{p} such that if n > n_{p}, then f(n,K^{p}) = ext(n,K^{p-1})+1, (where ext(n,K^{p-1}) is the maximum number of edges a graph on n vertices can contain without containing K^{p-1} as a subgraph). Further if K^{n} is colored by f(n,K^{p}) colors and contains no totally multicolored K^{p}, then its coloring is uniquely determined: one can divide the vertices of K^{n} into d classes A_{1}, ... ,A_{d} so that each edge joining vertices from different A_{i}'s has its own color (that is, a color used only once) and each edge (x,y) where x and y belong to the same A_{i} has the same color independent from x, y and i. Conjecture 1. Let C^{k} denote the k-circuit. Then f(n,C^{k})-n((k-2)/2+1/(k-1))+0(1).

**Reviewer: ** J.E.Graver

**Classif.: ** * 05C15 Chromatic theory of graphs and maps

05C35 Extremal problems (graph theory)

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag