Subgraphs with a large cochromatic number

Noga Alon, Michael Krivelevich, Benny SundakovJournal of Graph Theory 1997 · DOI

Abstract

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 . This is tight, up to the constant factor, and settles a problem of Erdös and Gimbel. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 295–297, 1997
BibTeX
@article{alon1997subgraphs,
  author = {Noga Alon and Michael Krivelevich and Benny Sundakov},
  title = {{Subgraphs with a large cochromatic number}},
  journal = {Journal of Graph Theory},
  year = {1997},
  doi = {10.1002/(sici)1097-0118(199708)25:4<295::aid-jgt7>3.0.co;2-f},
}

Loading related content...

Figure