2022/07/23 by Xiutao Zhu, Yaojun Chen, Zhu, Xiutao +1 · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2207.11506
openalex publication_date 2022/07/23 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28
The Turán number ex(n,H) is the maximum number of edges in an H-free graph on n vertices. Let T be any tree. The odd-ballooning of T, denoted by To, is a graph obtained by replacing each edge of T with an odd cycle containing the edge, and all new vertices of the odd cycles are distinct. In this paper, we determine the exact value of ex(n,To) for sufficiently large n and To being good, which generalizes all the known results on ex(n,To) for T being a star, due to Erdős et al. (1995), Hou et al. (2018) and Yuan (2018), and provides some counterexamples with chromatic number 3 to a conjecture of Keevash and Sudakov (2004), on the maximum number of edges not in any monochromatic copy of H in a 2-edge-coloring of a complete graph of order n.