1. Turán number for odd‐ballooning of trees.
- Author
-
Zhu, Xiutao and Chen, Yaojun
- Subjects
- *
RAMSEY numbers , *COMPLETE graphs , *TREES - Abstract
The Turán number ex(n,H) $\text{ex}(n,H)$ is the maximum number of edges in an H $H$‐free graph on n $n$ vertices. Let T $T$ be any tree. The odd‐ballooning of T $T$, denoted by To ${T}_{o}$, is a graph obtained by replacing each edge of T $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) $\text{ex}(n,{T}_{o})$ for sufficiently large n $n$ and To ${T}_{o}$ being good, which generalizes all the known results on ex(n,To) $\text{ex}(n,{T}_{o})$ for T $T$ being a star, due to Erdős, Füredi, Gould, and Gunderson (1995), Hou, Qiu, and Liu (2018), and Yuan (2018), and provides some counterexamples with chromatic number three to a conjecture of Keevash and Sudakov (2004), on the maximum number of edges not in any monochromatic copy of H $H$ in a 2‐edge‐coloring of a complete graph of order n $n$. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF