On the editing distance of graphs

DOI10.1002/jgt.20296zbMath1156.05027arXivmath/0606475OpenAlexW2949874554MaRDI QIDQ3506314

Ryan R. Martin, André E. Kézdy, Maria A. Axenovich

Publication date: 12 June 2008

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

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

zbMATH Keywords

regularity lemmaedit distanceforbidden induced subgraphbinary chromatic number

Mathematics Subject Classification ID

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

Related Items (18)

Partitioning a Graph into Highly Connected Subgraphs ⋮ Edit distance measure for graphs ⋮ A Brooks‐Type Theorem for the Bichromatic Number ⋮ On the Edit Distance from K2,t-Free Graphs ⋮ The edit distance function of some graphs ⋮ The edit distance function and symmetrization ⋮ The regularity of almost all edge ideals ⋮ Differential calculus on the space of countable labelled graphs ⋮ The structure of hereditary properties and 2-coloured multigraphs ⋮ On the computation of edit distance functions ⋮ \((k,l)\)-colourings and Ferrers diagram representations of cographs ⋮ Graph distance measures based on topological indices revisited ⋮ A note on the bichromatic numbers of graphs ⋮ Sparse graphs: Metrics and random models ⋮ A comparative analysis of new graph distance measures and graph edit distance ⋮ Editing to prime graphs ⋮ On the edit distance of powers of cycles ⋮ Stability‐type results for hereditary properties

Cites Work

• Hereditary properties of graphs: Asymptotic enumeration, global structure, and colouring

This page was built for publication: On the editing distance of graphs