
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.
anti-Ramsey numbers, Computational Theory and Mathematics, Generalized Ramsey theory, Discrete Mathematics and Combinatorics, Turán numbers, Theoretical Computer Science
anti-Ramsey numbers, Computational Theory and Mathematics, Generalized Ramsey theory, Discrete Mathematics and Combinatorics, Turán numbers, Theoretical Computer Science
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 24 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
