Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  791.05037
Autor:  Erdös, Paul; Tuza, Zsolt
Title:  Rainbow subgraphs in edge-colorings of complete graphs. (In English)
Source:  Gimbel, John (ed.) et al., Quo vadis, graph theory? A source book for challenges and directions. Amsterdam: North-Holland, Ann. Discrete Math. 55, 81-88 (1993).
Review:  We raise the following problem. Let F be a given graph with e edges. Consider the edge colorings of Kn (n large) with e colors, such that every vertex has degree at least d in each color (d < n/e). For which values of d does every such edge coloring contain a subgraph isomorphic to F, all of whose edges have distinct colors? The case when F is the triangle K3 is well-understood, but for other graphs F many interesting questions remain open, even for d-regular colorings when n = de+1.
Classif.:  * 05C15 Chromatic theory of graphs and maps
Keywords:  rainbow subgraphs; complete graphs; edge colorings

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page