Abstract
We address a problem which is a generalization of Turán-type problems recently introduced by Imolay, Karl, Nagy, and Váli. Let F be a fixed graph and let G be the union of k edge-disjoint copies of F, namely G = ∪ ki=1Fi, where each Fi is isomorphic to a fixed graph F and E(Fi) ∩ E(Fj) = ∅ for all i ≠ j. We call a subgraph H ⊆ G multicolored if H and Fi share at most one edge for all i. Define exF (H, n) to be the maximum value k such that there exists G = ∪ ki=1Fi on n vertices without a multicolored copy of H. We show that exC5 (C3, n) ≤ n2/25 + 3n/25 + o(n) and that all extremal graphs are close to a blow-up of the 5-cycle. This bound is tight up to the linear error term.
Original language | English (US) |
---|---|
Pages (from-to) | 2297-2311 |
Number of pages | 15 |
Journal | SIAM Journal on Discrete Mathematics |
Volume | 38 |
Issue number | 3 |
DOIs | |
State | Published - 2024 |
ASJC Scopus subject areas
- General Mathematics