Subgraphs with a Large Cochromatic Number

Noga Alon, Michael Krivelevich, Benny Sudakov

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


The cochromatic number of a graph G = (V, E) is the smallest number of parts in a partition of V in which each part is either an independent set or induces a complete subgraph. We show that if the chromatic number of G is n, then G contains a subgraph with cochromatic number at least Ω(n/lnn). This is tight, up to the constant factor, and settles a problem of Erdos and Gimbel.

Original languageEnglish (US)
Pages (from-to)295-297
Number of pages3
JournalJournal of Graph Theory
Issue number4
StatePublished - Aug 1997
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Geometry and Topology


  • Chromatic number
  • Graph coloring
  • Ramsey theory


Dive into the research topics of 'Subgraphs with a Large Cochromatic Number'. Together they form a unique fingerprint.

Cite this