Subgraphs with a large cochromatic number
Lists
Only you see this
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...