Easily Testable Graph Properties

DOI10.1017/S0963548314000765zbMath1371.05136WikidataQ105585016 ScholiaQ105585016MaRDI QIDQ5364250

Noga Alon, Jacob Fox

Publication date: 4 October 2017

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Testing graphs against an unknown distribution, A characterization of easily testable induced digraphs and \(k\)-colored graphs, Polynomial removal lemmas for ordered graphs, Fast Property Testing and Metrics for Permutations, Efficient Removal Lemmas for Matrices, Efficient removal lemmas for matrices, On 3‐graphs with no four vertices spanning exactly two edges, Estimating the distance to a hereditary graph property, A Polynomial Regularity Lemma for Semialgebraic Hypergraphs and Its Applications in Geometry and Property Testing, The Bradley-Terry condition is \(L_1\)-testable, On Rödl's theorem for cographs, Local-vs-global combinatorics, Unnamed Item, Efficient Testing without Efficient Regularity, On the Query Complexity of Estimating the Distance to Hereditary Graph Properties

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new proof of the graph removal lemma
• The strong perfect graph theorem
• Geometric algorithms and combinatorial optimization
• Packing and covering triangles in graphs
• Bounds for graph regularity and removal lemmas
• Recognizing Berge graphs
• On a property of the class of n-colorable graphs
• A decomposition theorem for partially ordered sets
• Property testing and its connection to learning and approximation
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• The Algorithmic Aspects of the Regularity Lemma
• Three theorems regarding testing graph properties
• Testing subgraphs in large graphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• Probability Inequalities for Sums of Bounded Random Variables
• Transitiv orientierbare Graphen
• On Certain Sets of Integers
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
• Efficient testing of large graphs