Every Monotone 3-Graph Property is Testable

DOI10.1016/j.endm.2005.06.086zbMath1200.05213OpenAlexW2072500969MaRDI QIDQ3439395

Mathias Schacht, Christian Avart, Vojtěch Rödl

Publication date: 29 May 2007

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2005.06.086

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• On graphs with small subgraphs of large chromatic number
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• Property testing and its connection to learning and approximation
• Every monotone graph property is testable
• The Algorithmic Aspects of the Regularity Lemma
• Robust Characterizations of Polynomials with Applications to Program Testing
• Regular Partitions of Hypergraphs: Regularity Lemmas
• Efficient testing of large graphs