Every minor-closed property of sparse graphs is testable
From MaRDI portal
Publication:962147
DOI10.1016/j.aim.2009.10.018zbMath1223.05291arXiv0801.2797MaRDI QIDQ962147
Itai Benjamini, Oded Schramm, Asaf Shapira
Publication date: 6 April 2010
Published in: Advances in Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0801.2797
05C83: Graph minors
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Graph minors. XX: Wagner's conjecture
- Lower bound of the Hadwiger number of graphs by their average degree
- Hyperfinite graph limits
- Testing the expansion of a graph
- Self-testing/correcting with applications to numerical problems
- The extremal function for complete minors
- A sublinear bipartiteness tester for bounded degree graphs
- The combinatoral cost
- Graph limits and parameter testing
- Parameter testing in bounded degree graphs of subexponential growth
- On Testing Expansion in Bounded-Degree Graphs
- Property testing and its connection to learning and approximation
- An extremal function for contractions of graphs
- Graph minor theory
- A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
- Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
- A Separator Theorem for Planar Graphs
- Applications of a Planar Separator Theorem
- A Separator Theorem for Nonplanar Graphs
- Efficient Planarity Testing
- Testing the diameter of graphs
- Robust Characterizations of Polynomials with Applications to Program Testing
- Local Graph Partitions for Approximation and Testing
- A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
- SOFSEM 2005: Theory and Practice of Computer Science
- An Expansion Tester for Bounded Degree Graphs
- Property testing in bounded degree graphs
