Testing k-colorability
From MaRDI portal
Publication:2784512
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
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Related Items
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
