Subgraphs with a Large Cochromatic Number

Noga Alon; Michael Krivelevich; Benny Sudakov

doi:10.1002/(SICI)1097-0118(199708)25:4<295::AID-JGT7>3.0.CO;2-F

Subgraphs with a Large Cochromatic Number

Noga Alon, Michael Krivelevich, Benny Sudakov

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

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 Ω(n/lnn). This is tight, up to the constant factor, and settles a problem of Erdos and Gimbel.

Original language	English (US)
Pages (from-to)	295-297
Number of pages	3
Journal	Journal of Graph Theory
Volume	25
Issue number	4
DOIs	https://doi.org/10.1002/(SICI)1097-0118(199708)25:4<295::AID-JGT7>3.0.CO;2-F
State	Published - Aug 1997
Externally published	Yes

All Science Journal Classification (ASJC) codes

Geometry and Topology

Keywords

Chromatic number
Graph coloring
Ramsey theory

Access to Document

10.1002/(SICI)1097-0118(199708)25:4<295::AID-JGT7>3.0.CO;2-F

Cite this

@article{6dc390061ba34bd6956777065b5866a3,

title = "Subgraphs with a Large Cochromatic Number",

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 Ω(n/lnn). This is tight, up to the constant factor, and settles a problem of Erdos and Gimbel.",

keywords = "Chromatic number, Graph coloring, Ramsey theory",

author = "Noga Alon and Michael Krivelevich and Benny Sudakov",

year = "1997",

month = aug,

doi = "10.1002/(SICI)1097-0118(199708)25:4<295::AID-JGT7>3.0.CO;2-F",

language = "English (US)",

volume = "25",

pages = "295--297",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "4",

}

TY - JOUR

T1 - Subgraphs with a Large Cochromatic Number

AU - Alon, Noga

AU - Krivelevich, Michael

AU - Sudakov, Benny

PY - 1997/8

Y1 - 1997/8

N2 - 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.

AB - 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.

KW - Chromatic number

KW - Graph coloring

KW - Ramsey theory

UR - http://www.scopus.com/inward/record.url?scp=0031475889&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0031475889&partnerID=8YFLogxK

U2 - 10.1002/(SICI)1097-0118(199708)25:4<295::AID-JGT7>3.0.CO;2-F

DO - 10.1002/(SICI)1097-0118(199708)25:4<295::AID-JGT7>3.0.CO;2-F

M3 - Article

AN - SCOPUS:0031475889

SN - 0364-9024

VL - 25

SP - 295

EP - 297

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 4

ER -

Subgraphs with a Large Cochromatic Number

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this