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

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

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

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

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Unnamed Item ⋮ Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On graphs with small subgraphs of large chromatic number
• A sublinear bipartiteness tester for bounded degree graphs
• Testing k-colorability
• A combinatorial characterization of the testable graph properties
• Property testing and its connection to learning and approximation
• Approximating average parameters of graphs
• Testing triangle-freeness in general graphs
• Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
• On circuits and subgraphs of chromatic graphs
• Two-dimensional weight-constrained codes through enumeration bounds
• Testing the diameter of graphs
• Tight Bounds for Testing Bipartiteness in General Graphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
• Efficient testing of large graphs
• Property testing in bounded degree graphs