Anti-Ramsey Numbers of Subdivided Graphs

AbstractGiven a positive integer n and a family F of graphs, the anti-Ramsey numberf(n, F) is the maximum number of colors in an edge-coloring of Kn such that no subgraph of Kn belonging to F has distinct colors on its edges. The Turán numberex(n, F) is the maximum number of edges of an n-vertex graph that does not contain a member of F as a subgraph. P. Erdős 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(n2), where H={H−e:e∈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