What is the furthest graph from a hereditary property?

DOI10.1002/rsa.20209zbMath1146.05046OpenAlexW4246317086MaRDI QIDQ3522831

Uri Stav, Noga Alon

Publication date: 4 September 2008

Published in: Random Structures and Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20209

zbMATH Keywords

random graphsmaximal distanceedit distanceedge removalmonotone graph propertyhereditary graph propertiesvertex removalregularity LemmaSzemeredi regularity lemmaalgorithmis edge-modification problemsedge modifications

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Related Items (15)

On the edit distance function of the random graph ⋮ Accumulation points of the edit distance function ⋮ Partitioning a Graph into Highly Connected Subgraphs ⋮ Edit distance measure for graphs ⋮ On the Edit Distance from K2,t-Free Graphs ⋮ The edit distance function of some graphs ⋮ Testing properties of graphs and functions ⋮ The edit distance function and symmetrization ⋮ Largest subgraph from a hereditary property in a random graph ⋮ The structure of hereditary properties and 2-coloured multigraphs ⋮ On the computation of edit distance functions ⋮ The maximum edit distance from hereditary graph properties ⋮ On the edit distance of powers of cycles ⋮ Hardness of edge-modification problems ⋮ Stability‐type results for hereditary properties

Cites Work

• Graph limits and parameter testing
• Unnamed Item

This page was built for publication: What is the furthest graph from a hereditary property?