Testing k-colorability

DOI10.1137/S0895480199358655zbMath1001.05058OpenAlexW2000079459MaRDI QIDQ2784512

Noga Alon, Michael Krivelevich

Publication date: 23 April 2002

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480199358655

zbMATH Keywords

graph coloringproperty testing

Mathematics Subject Classification ID

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

Related Items (17)

Property testing of the Boolean and binary rank ⋮ Testing Odd-Cycle-Freeness in Boolean Functions ⋮ A lower bound for testing juntas ⋮ On the benefits of adaptivity in property testing of dense graphs ⋮ Comparing the strength of query types in property testing: the case of \(k\)-colorability ⋮ Unnamed Item ⋮ Generating all subsets of a finite set with disjoint unions ⋮ Introduction to Testing Graph Properties ⋮ \(\omega\)-regular languages are testable with a constant number of queries ⋮ Testing hypergraph colorability ⋮ Comparing the Strength of Query Types in Property Testing: The Case of Testing k-Colorability ⋮ Fast distributed algorithms for testing graph properties ⋮ Testing subgraphs in directed graphs ⋮ Introduction to Testing Graph Properties ⋮ Contemplations on Testing Graph Properties ⋮ Planar graphs: Random walks and bipartiteness testing ⋮ Unnamed Item

This page was built for publication: Testing k-colorability