Turán number for odd‐ballooning of trees

DOI10.1002/JGT.22959MaRDI QIDQ6094026zbMATH OpenOpenAlexFDO

Authors Xiutao Zhu, Yaojun Chen

Publication date 9 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2207.11506

zbMATH Keywords

decomposition familyodd-ballooningtreeTurán number

Mathematics Subject Classification ID

Trees (05C05) Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75)

Abstract: The Tur'an 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 $T_o$, 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,T_o)$ for sufficiently large $n$ and $T_o$ being good, which generalizes all the known results on $ex(n,T_o)$ for $T$ being a star, due to ErdH{o}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$.

Recommendations

• The Turán number of blow-ups of trees
• The Turán number for the edge blow-up of trees
• Turán's problem for trees
• Turán numbers of Berge trees
• Turán's problem and Ramsey numbers for trees
• On the Turán number of forests
• Integral trees of odd diameters
• The Turán number for spanning linear forests
• The Turán number for the edge blow-up of trees: the missing case
• On the Balaban index of trees

Cites work

• Degrees and matchings
• Edges not in any monochromatic copy of a fixed graph
• Extremal graph for intersecting odd cycles
• Extremal graph problems with symmetrical extremal graphs. Additional chromatic conditions
• Extremal graphs for blow-ups of cycles and trees
• Extremal graphs for edge blow-up of graphs
• Extremal graphs for intersecting cliques
• Extremal graphs for intersecting triangles
• Extremal graphs for the k-flower
• scientific article; zbMATH DE number 3285073 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• Intersection theorems for systems of sets
• On edges not in monochromatic copies of a fixed bipartite graph
• On the number of edges not covered by monochromatic copies of a fixed graph.
• On the structure of linear graphs
• The Turán number for the edge blow-up of trees
• Turán number and decomposition number of intersecting odd cycles

Cited in

(6)

• Turán numbers for odd wheels
• Extremal graphs for odd-ballooning of paths and cycles
• The Turán number of blow-ups of trees
• Turán's problem for trees
• Edges Not Covered by Monochromatic Bipartite Graph
• Turán number of the odd-ballooning of complete bipartite graphs

This page was built for publication: Turán number for odd‐ballooning of trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6094026)