Clique coloring of dense random graphs

Noga Alon; Michael Krivelevich

doi:10.1002/jgt.22222

Clique coloring of dense random graphs

Noga Alon, Michael Krivelevich

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

5 Scopus citations

Abstract

The clique chromatic number of a graph G=(V.E) is the minimum number of colors in a vertex coloring so that no maximal (with respect to containment) clique is monochromatic. We prove that the clique chromatic number of the binomial random graph G=G(n,1/2) is, with high probability, Ω(log n). This settles a problem of McDiarmid, Mitsche, and Prałat who proved that it is O(log n) with high probability.

Original language	English (US)
Pages (from-to)	428-433
Number of pages	6
Journal	Journal of Graph Theory
Volume	88
Issue number	3
DOIs	https://doi.org/10.1002/jgt.22222
State	Published - Jul 2018
Externally published	Yes

All Science Journal Classification (ASJC) codes

Geometry and Topology

Keywords

cliques
coloring
random graphs

Access to Document

10.1002/jgt.22222

Cite this

@article{ae8fbde0fca6450c83fd580e884b8cf7,

title = "Clique coloring of dense random graphs",

abstract = "The clique chromatic number of a graph G=(V.E) is the minimum number of colors in a vertex coloring so that no maximal (with respect to containment) clique is monochromatic. We prove that the clique chromatic number of the binomial random graph G=G(n,1/2) is, with high probability, Ω(log n). This settles a problem of McDiarmid, Mitsche, and Pra{\l}at who proved that it is O(log n) with high probability.",

keywords = "cliques, coloring, random graphs",

author = "Noga Alon and Michael Krivelevich",

note = "Publisher Copyright: {\textcopyright} 2017 Wiley Periodicals, Inc.",

year = "2018",

month = jul,

doi = "10.1002/jgt.22222",

language = "English (US)",

volume = "88",

pages = "428--433",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "3",

}

TY - JOUR

T1 - Clique coloring of dense random graphs

AU - Alon, Noga

AU - Krivelevich, Michael

PY - 2018/7

Y1 - 2018/7

N2 - The clique chromatic number of a graph G=(V.E) is the minimum number of colors in a vertex coloring so that no maximal (with respect to containment) clique is monochromatic. We prove that the clique chromatic number of the binomial random graph G=G(n,1/2) is, with high probability, Ω(log n). This settles a problem of McDiarmid, Mitsche, and Prałat who proved that it is O(log n) with high probability.

AB - The clique chromatic number of a graph G=(V.E) is the minimum number of colors in a vertex coloring so that no maximal (with respect to containment) clique is monochromatic. We prove that the clique chromatic number of the binomial random graph G=G(n,1/2) is, with high probability, Ω(log n). This settles a problem of McDiarmid, Mitsche, and Prałat who proved that it is O(log n) with high probability.

KW - cliques

KW - coloring

KW - random graphs

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

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

U2 - 10.1002/jgt.22222

DO - 10.1002/jgt.22222

M3 - Article

AN - SCOPUS:85046907949

SN - 0364-9024

VL - 88

SP - 428

EP - 433

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 3

ER -

Clique coloring of dense random graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this