A stability theorem for maximal C2k+1 {C}_{2k+1}‐free graphs

DOI10.1002/JGT.22824MaRDI QIDQ6081589zbMATH OpenOpenAlexWikidataFDO

Authors Jian Wang, Shipeng Wang, Weihua Yang, Xiaoli Yuan

Publication date 5 October 2023

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

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

zbMATH Keywords

maximal \(C_{2k+1}\)-freeodd cyclestability theoremTurán theorem

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: For any positive integer $k$, we show that every maximal $C_{2k+1}$-free graph with at least $n^2/4-o(n^{3/2})$ edges contains an induced complete bipartite subgraph on $(1-o(1))n$ vertices. We also show that this is best possible.

Recommendations

• A stability theorem for maximal \(K_{r+1}\)-free graphs
• Turán number of an induced complete bipartite graph plus an odd cycle
• A note on stability for maximal \(F\)-free graphs
• On subgraphs of \(C_{2k}\)-free graphs and a problem of Kühn and Osthus
• On subgraphs of \(C_{2k}\)-free graphs

Cites work

• A Bound on the Number of Edges in Graphs Without an Even Cycle
• A note on stability for maximal \(F\)-free graphs
• A note on Turán numbers for even wheels
• A stability theorem for maximal \(K_{r+1}\)-free graphs
• Exact stability for Turán's theorem
• Extremal graph problems with symmetrical extremal graphs. Additional chromatic conditions
• Extremal numbers for odd cycles
• scientific article; zbMATH DE number 3691361 (Why is no real title available?)
• scientific article; zbMATH DE number 3258858 (Why is no real title available?)
• scientific article; zbMATH DE number 3298603 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• Large cycles in graphs
• Many \(T\) copies in \(H\)-free graphs
• On maximal paths and circuits of graphs
• On the connection between chromatic number, maximal clique and minimal degree of a graph
• Pancyclic graphs. I
• Stability results for random discrete structures
• Strong Turán stability
• Sufficient Conditions for Circuits in Graphs^†
• THE NUMBER OF EDGE COLORINGS WITH NO MONOCHROMATIC CLIQUES
• Unit distances and diameters in Euclidean spaces

Cited in

(12)

• A note on stability for maximal \(F\)-free graphs
• Badly-covered graphs
• On the non-(p-1)-partite K_p-free graphs
• Basic maximal 2K₂-free graphs
• A CHARACTERIZATION OF STABLE GRAPHS ON A MAXIMUM(MINIMUM) NUMBER OF EDGES
• On subgraphs of \(C_{2k}\)-free graphs and a problem of Kühn and Osthus
• Turán number of an induced complete bipartite graph plus an odd cycle
• Counterexamples to Gerbner's conjecture on stability of maximal F‐free graphs
• A stability result for $C_{2k+1}$-free graphs
• Minimum degree stability of \({C}_{2k+1}\)-free graphs
• Two stability theorems for \(\mathcal{K}_{\ell + 1}^r\)-saturated hypergraphs
• A stability theorem for maximal \(K_{r+1}\)-free graphs

This page was built for publication: A stability theorem for maximal C2k+1 ${C}_{2k+1}$‐free graphs

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