Comparing the strength of query types in property testing: the case of \(k\)-colorability

DOI10.1007/s00037-012-0048-2zbMath1280.68091MaRDI QIDQ1947037

Dana Ron, Michael Krivelevich, Tali Kaufman, Ido Ben-Eliezer

Publication date: 11 April 2013

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-012-0048-2

zbMATH Keywords

property testing; \(k\)-colorability

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C15: Coloring of graphs and hypergraphs

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)