Every minor-closed property of sparse graphs is testable
From MaRDI portal
Publication:962147
DOI10.1016/j.aim.2009.10.018zbMath1223.05291arXiv0801.2797OpenAlexW2569976290MaRDI 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
Related Items
Planarity can be verified by an approximate proof labeling scheme in constant-time, Local 2-separators, Faster Property Testers in a Variation of the Bounded Degree Model, Graph theory. Abstracts from the workshop held January 2--8, 2022, Unnamed Item, Hyperfinite graphings and combinatorial optimization, Limits of locally-globally convergent graph sequences, On the tree-width of even-hole-free graphs, Testing outerplanarity of bounded degree graphs, Finite graphs and amenability, An analytic approach to stability, Unnamed Item, Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs, Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs, Planar graphs: Random walks and bipartiteness testing, Edge Correlations in Random Regular Hypergraphs and Applications to Subgraph Testing, An explicit construction of graphs of bounded degree that are far from being Hamiltonian
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
