The maximum edit distance from hereditary graph properties
From MaRDI portal
Publication:933672
DOI10.1016/j.jctb.2007.10.001zbMath1156.05026OpenAlexW2092951014MaRDI QIDQ933672
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
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
