Clique coverings of the edges of a random graph

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

Research output: Contribution to journalArticlepeer-review


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 .

Original languageEnglish (US)
Pages (from-to)1-5
Number of pages5
Issue number1
StatePublished - Mar 1993


  • AMS subject classification code (1991): 05C80

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics


Dive into the research topics of 'Clique coverings of the edges of a random graph'. Together they form a unique fingerprint.

Cite this