Comparing the Strength of Query Types in Property Testing: The Case of Testing k-Colorability

DOI10.1007/978-3-642-16367-8_17zbMath1309.68215OpenAlexW2125719181MaRDI QIDQ4933375

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

Publication date: 12 October 2010

Published in: Property Testing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-16367-8_17

zbMATH Keywords

\(k\)-colorabilitygroup queriesneighbor queriespair queries

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Randomized algorithms (68W20)

Cites Work

• 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
• Testing the diameter of graphs
• Tight Bounds for Testing Bipartiteness in General Graphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• Efficient testing of large graphs
• Property testing in bounded degree graphs

This page was built for publication: Comparing the Strength of Query Types in Property Testing: The Case of Testing k-Colorability