The maximum edit distance from hereditary graph properties

DOI10.1016/j.jctb.2007.10.001zbMath1156.05026OpenAlexW2092951014MaRDI QIDQ933672

Noga Alon, Uri Stav

Publication date: 24 July 2008

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2007.10.001

zbMATH Keywords

random graphshereditary propertiesedit distanceregularity Lemma

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Distance in graphs (05C12)

Related Items

On the edit distance function of the random graph, Obstructions for partitioning into forests and outerplanar graphs, A Brooks‐Type Theorem for the Bichromatic Number, Deviation estimates for Eulerian edit numbers of random graphs, The edit distance function and symmetrization, On the computation of edit distance functions, \((k,l)\)-colourings and Ferrers diagram representations of cographs, A proof of the stability of extremal graphs, Simonovits' stability from Szemerédi's regularity, Graph distance measures based on topological indices revisited, A note on the bichromatic numbers of graphs, Excluding induced subgraphs: Critical graphs, A comparative analysis of new graph distance measures and graph edit distance, Hardness of edge-modification problems, Stability‐type results for hereditary properties, Quantitative graph theory: a new branch of graph theory and network science

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Excluding induced subgraphs. II: Extremal graphs
• Complement reducible graphs
• On the size of hereditary classes of graphs
• On the connection between chromatic number, maximal clique and minimal degree of a graph
• The speed of hereditary properties of graphs
• On a valence problem in extremal graph theory
• What is the furthest graph from a hereditary property?
• Cutting a graph into two dissimilar halves
• Excluding induced subgraphs: quadrilaterals
• Excluding Induced Subgraphs III: A General Asymptotic
• On the entropy values of hereditary classes of graphs
• Topics in Intersection Graph Theory
• Generalized chromatic numbers of random graphs
• Projections of Bodies and Hereditary Properties of Hypergraphs
• Avoiding Patterns in Matrices Via a Small Number of Changes
• Lower Bounds for Approximation by Nonlinear Manifolds
• On the structure of linear graphs
• The structure of hereditary properties and colourings of random graphs
• Efficient testing of large graphs
• The penultimate rate of growth for graph properties