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 Kn, 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 np such that if n > np, then f(n,Kp) = ext(n,Kp-1)+1, (where ext(n,Kp-1) is the maximum number of edges a graph on n vertices can contain without containing Kp-1 as a subgraph). Further if Kn is colored by f(n,Kp) colors and contains no totally multicolored Kp, then its coloring is uniquely determined: one can divide the vertices of Kn into d classes A1, ... ,Ad so that each edge joining vertices from different Ai'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 Ai has the same color independent from x, y and i. Conjecture 1. Let Ck denote the k-circuit. Then f(n,Ck)-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