Testing k-colorability

Noga Alon, Michael Krivelevich

Research output: Contribution to journalArticlepeer-review

62 Scopus citations

Abstract

Let G be a graph on n vertices and suppose that at least εn2 edges have to be deleted from it to make it k-colorable. It is shown that in this case most induced subgraphs of G on ck ln k/ε2 vertices are not k-colorable, where c > 0 is an absolute constant. If G is as above for k = 2, then most induced subgraphs on (ln(1/ε))b/ε are nonbipartite, for some absolute positive constant b, and this is tight up to the polylogarithmic factor. Both results are motivated by the study of testing algorithms for k-colorability, first considered by Goldreich, Goldwasser, and Ron in [J. ACM, 45 (1998), pp. 653-750], and improve the results in that paper.

Original languageEnglish (US)
Pages (from-to)211-227
Number of pages17
JournalSIAM Journal on Discrete Mathematics
Volume15
Issue number2
DOIs
StatePublished - Feb 2002

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Graph coloring
  • Property testing

Fingerprint Dive into the research topics of 'Testing k-colorability'. Together they form a unique fingerprint.

Cite this