Clique coverings of the edges of a random graph

Béla Bollobás; Paul Erdos; Joel Spencer; Douglas B. West

doi:10.1007/BF01202786

Clique coverings of the edges of a random graph

Béla Bollobás, Paul Erdos, Joel Spencer, Douglas B. West

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

Abstract

The edges of the random graph (with the edge probability p=1/2) can be covered using O(n ² lnln n/(ln n) ² ) cliques. Hence this is an upper bound on the intersection number (also called clique cover number) of the random graph. A lower bound, obtained by counting arguments, is (1-e{open})n ² /(2lg n) ² .

Original language	English (US)
Pages (from-to)	1-5
Number of pages	5
Journal	Combinatorica
Volume	13
Issue number	1
DOIs	https://doi.org/10.1007/BF01202786
State	Published - Mar 1993

Keywords

AMS subject classification code (1991): 05C80

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Computational Mathematics

Access to Document

10.1007/BF01202786

Cite this

@article{54a75858bdbd40ae93fc65e6472f1736,

title = "Clique coverings of the edges of a random graph",

abstract = " The edges of the random graph (with the edge probability p=1/2) can be covered using O(n 2 lnln n/(ln n) 2 ) cliques. Hence this is an upper bound on the intersection number (also called clique cover number) of the random graph. A lower bound, obtained by counting arguments, is (1-e{open})n 2 /(2lg n) 2 .",

keywords = "AMS subject classification code (1991): 05C80",

author = "B{\'e}la Bollob{\'a}s and Paul Erdos and Joel Spencer and West, {Douglas B.}",

year = "1993",

month = mar,

doi = "10.1007/BF01202786",

language = "English (US)",

volume = "13",

pages = "1--5",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "1",

}

TY - JOUR

T1 - Clique coverings of the edges of a random graph

AU - Bollobás, Béla

AU - Erdos, Paul

AU - Spencer, Joel

AU - West, Douglas B.

PY - 1993/3

Y1 - 1993/3

N2 - The edges of the random graph (with the edge probability p=1/2) can be covered using O(n 2 lnln n/(ln n) 2 ) cliques. Hence this is an upper bound on the intersection number (also called clique cover number) of the random graph. A lower bound, obtained by counting arguments, is (1-e{open})n 2 /(2lg n) 2 .

AB - The edges of the random graph (with the edge probability p=1/2) can be covered using O(n 2 lnln n/(ln n) 2 ) cliques. Hence this is an upper bound on the intersection number (also called clique cover number) of the random graph. A lower bound, obtained by counting arguments, is (1-e{open})n 2 /(2lg n) 2 .

KW - AMS subject classification code (1991): 05C80

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

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

U2 - 10.1007/BF01202786

DO - 10.1007/BF01202786

M3 - Article

AN - SCOPUS:0042213605

VL - 13

SP - 1

EP - 5

JO - Combinatorica

JF - Combinatorica

SN - 0209-9683

IS - 1

ER -

Clique coverings of the edges of a random graph

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this