Given a positive integer n and a family. F of graphs, the anti-Ramsey number f(n, F) is the maximum number of colors in an edge-coloring of K such that no subgraph of K-n belonging to F has distinct colors on its edges. The Turan number ex(n, F) is the maximum number of edges of an n-vertex graph that does not contain a member of,a as a subgraph. P. Erdos et al. (1975, in Colloq. Math. Soc. Janos Bolyai, Vol. 10, pp. 633-643, North-Holland, Amsterdam) showed for all graphs H that f(n, H)-ex(n, H) = o(n(2)), where H = {H-e: e is an element of E(H)}. We strengthen their result for the class of graphs in which each edge is incident to a vertex of degree two. We show that f(n, H)-ex(n, H) = O(n) when H belongs to this class. This follows from a new upper bound on f(n. H) that we prove for all graphs H and asymptotically determines f(n, H) for certain graphs H. (C) 2002 Elsevier Science (USA). [References: 9]
展开▼
