Testing some first-order logic properties on sparse graphs
From MaRDI portal
Cites work
- A characterization of graph properties testable for general planar graphs with one-sided error (it's all about forbidden subgraphs)
- A combinatorial characterization of the testable graph properties, it's all about regularity
- A new method for generating Bonferroni-type inequalities by iteration
- Edge-Disjoint Spanning Trees of Finite Graphs
- Every minor-closed property of sparse graphs is testable
- Every property of hyperfinite graphs is testable
- Every property of outerplanar graphs is testable
- Graph theory with applications
- scientific article; zbMATH DE number 1179517 (Why is no real title available?)
- scientific article; zbMATH DE number 1559556 (Why is no real title available?)
- On testability of first-order properties in bounded-degree graphs and connections to proximity-oblivious testing
- Parameterized testability
- Planar Graphs: Random Walks and Bipartiteness Testing
- Random walks and forbidden minors iii: poly-time partition oracles for minor-free graph classes
- Testability and local certification of monotone properties in minor-closed classes
- Testing C_k-freeness in bounded-arboricity graphs
- Testing forest-isomorphism in the adjacency list model
- Testing Hamiltonicity (And Other Problems) in Minor-Free Graphs
- Testing subdivision-freeness: property testing meets structural graph theory
- Testing the diameter of graphs
- The arboricity captures the complexity of sampling edges
- Tight Bounds for Testing Bipartiteness in General Graphs
This page was built for publication: Testing some first-order logic properties on sparse graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6866545)
