Premium
Subgraphs with a large cochromatic number
Author(s) -
Alon Noga,
Krivelevich Michael,
Sundakov Benny
Publication year - 1997
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199708)25:4<295::aid-jgt7>3.0.co;2-f
Subject(s) - combinatorics , mathematics , partition (number theory) , chromatic scale , induced subgraph , graph , induced subgraph isomorphism problem , discrete mathematics , graph factorization , graph power , line graph , vertex (graph theory) , voltage graph
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 $\Omega ({{n}\over{ln n}}$ . 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