Anti-Ramsey numbers of subdivided graphs (Q1850619): Difference between revisions

Given a coloring \(c\) of the edges of a graph \(G\), call a subgraph \(H\) of \(G\) rainbow if each of its edges is a different color. Given an integer \(n\) and a graph \(H\), let \(f(n, H)\) be the maximum number of colors of an edge-coloring of \(K_n\) admitting no rainbow copies of \(H\). Meanwhile, given a set \(\mathcal H\) of graphs, let \(\text{ex}(n, \mathcal H)\) be the maximum number of edges of a subgraph of \(K_n\) that does not admit any copies of any \(H \in \mathcal H\) as a subgraph. \textit{P. Erdős, M. Simonovits} and \textit{V. T. Sós} [``Anti-Ramsey theorems'', in: Infinite and Finite Sets, Colloq. Honour Paul Erdős, Keszthely 1973, Colloq. Math. Soc. Janos Bolyai 10, 633-643 (1975; Zbl 0316.05111)] proved that if \(\mathcal H = \{H - e: e\) an edge of \(H\}\), then \(f(n, H) - \text{ex}(n, \mathcal H) = o(n^2)\). The result of this paper is that for \(H\) a graph with every edge incident to a vertex of degree \(2\), \(f(n, H) - \text{ex}(n, \mathcal H) = O(n)\), which is established by proving that if \(\mathcal H_2\) is the set of graphs \(H - v\), \(v\) a vertex of degree \(2\), \(f(n, H) \leq \text{ex}(n, \mathcal H_2) + bn\), where \(b = \max \{2p - 2, q - 2\}\), \(p\) the number of vertices of \(H\) and \(q\) the number of edges.