A note on stability for maximal F-free graphs

DOI10.1007/S00373-021-02372-ZMaRDI QIDQ2053718zbMATH OpenOpenAlexFDO

Authors Dániel Gerbner

Publication date 30 November 2021

Published in Graphs and Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

color-criticalstabilityTurán theory

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35)

Abstract: Popielarz, Sahasrabudhe and Snyder in 2018 proved that maximal $K_{r+1}$-free graphs with $(1-frac1r)frac{n}^{2}2-o(n^{fracr+1r})$ edges contain a complete $r$-partite subgraph on $n-o(n)$ vertices. This was very recently extended to odd cycles in place of $K_3$ by Wang, Wang, Yang and Yuan. We further extend it to some other 3-chromatic graphs, and obtain some other stability results along the way.

Recommendations

• A stability theorem for maximal \(K_{r+1}\)-free graphs
• A stability theorem for maximal C2k+1 ${C}_{2k+1}$‐free graphs
• Stability results for graphs with a critical edge
• Strong Turán stability
• Maximum \(K_{r+1}\)-free graphs which are not \(r\)-partite.

Cites work

• A stability theorem for maximal \(K_{r+1}\)-free graphs
• Degrees and matchings
• Extremal graph problems with symmetrical extremal graphs. Additional chromatic conditions
• 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 3262986 (Why is no real title available?)
• 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
• Large generalized books are \(p\)-good
• Many \(T\) copies in \(H\)-free graphs
• On a problem of K. Zarankiewicz
• On a valence problem in extremal graph theory
• On the connection between chromatic number, maximal clique and minimal degree of a graph
• On the structure of linear graphs
• Stability results for graphs with a critical edge
• Strong Turán stability
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent

Cited in

(7)

• Stability in \(P_5\)- and banner-free graphs
• A remark on the stability of saturated generic graphs
• A CHARACTERIZATION OF STABLE GRAPHS ON A MAXIMUM(MINIMUM) NUMBER OF EDGES
• A stability theorem for maximal C2k+1 ${C}_{2k+1}$‐free graphs
• Counterexamples to Gerbner's conjecture on stability of maximal F‐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 note on stability for maximal \(F\)-free graphs

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