On the editing distance of graphs

DOI10.1002/jgt.20296zbMath1156.05027arXivmath/0606475MaRDI 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 lemma; edit distance; forbidden induced subgraph; binary chromatic number

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

05C80: Random graphs (graph-theoretic aspects)

05C12: Distance in graphs

Related Items

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

Cites Work

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