Zentralblatt MATH

Publications of (and about) Paul Erdös
Zbl.No:  682.05046
Autor:  Burr, Stefan A.; Erdös, Paul; Graham, Ronald L.; Sós, V.T.
Title:  Maximal anti-Ramsey graphs and the strong chromatic number. (In English)
Source:  J. Graph Theory 13, No.3, 263-282 (1989).
Review:  Let G and L denote two graphs. By \chis(G < L) we mean the minimum number of colors required to color the vertices of G so that any subgraph of G isomorphic to L has all of its vertices assigned different colors. Given integers n and e,

\chis(n,e,L) = maxG in G{\chis(G,L)}

where G is the class of all graphs on n vertices with e edges. Thus, \chis(n,e,L) is an ``extremal anti- Ramsey number''. This paper is devoted to the study of these numbers. It contains some specific values, some bounds and some asymptotic results. It closes with a discussion of several interesting open questions.
Reviewer:  J.E.Graver
Classif.:  * 05C55 Generalized Ramsey theory
                   05C15 Chromatic theory of graphs and maps
Keywords:  extremal anti-Ramsey number

© 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