On Multicolor Turán Numbers

József Balogh, Anita Liebenau, Letícia Mattos, Natasha Morrison

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)2297-2311
Number of pages15
JournalSIAM Journal on Discrete Mathematics
Volume38
Issue number3
DOIs
StatePublished - 2024

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

Dive into the research topics of 'On Multicolor Turán Numbers'. Together they form a unique fingerprint.

Cite this