CLIQUE COVERINGS OF THE EDGES OF A RANDOM GRAPH

被引：11

作者：

BOLLOBAS, B

ERDOS, P

SPENCER, J

WEST, DB

机构：

[1] COURANT INST,NEW YORK,NY

[2] LOUISIANA STATE UNIV,BATON ROUGE,LA 70803

[3] UNIV CAMBRIDGE,CAMBRIDGE,ENGLAND

[4] HUNGARIAN ACAD SCI,H-1361 BUDAPEST 5,HUNGARY

[5] UNIV ILLINOIS,URBANA,IL 61801

来源：

COMBINATORICA | 1993年 / 13卷 / 01期

关键词：

D O I：

10.1007/BF01202786

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The edges of the random graph (with the edge probability p = 1/2) can be covered using O(n2 ln ln 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 - epsilon)n2/(2 lg n)2.

引用

页码：1 / 5

页数：5

共 8 条

[1]

BOLLOBAS B, 1988, COMBINATORICA, V8

[2] REPRESENTATION OF A GRAPH BY SET INTERSECTIONS [J].

ERDOS, P ;

GOODMAN, AW ;

POSA, L .

CANADIAN JOURNAL OF MATHEMATICS, 1966, 18 (01) :106-&

[3] A NOTE ON THE INTERVAL NUMBER OF A GRAPH [J].

ERDOS, P ;

WEST, DB .

DISCRETE MATHEMATICS, 1985, 55 (02) :129-133

[4] EXTREMAL VALUES OF THE INTERVAL NUMBER OF A GRAPH [J].

GRIGGS, JR ;

WEST, DB .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1980, 1 (01) :1-7

[5] EXTREMAL VALUES OF THE INTERVAL NUMBER OF A GRAPH .2. [J].

GRIGGS, JR .

DISCRETE MATHEMATICS, 1979, 28 (01) :37-47

[6]

Matula DW., 1976, LARGEST CLIQUE SIZE

[7] ON THE INTERVAL NUMBER OF RANDOM GRAPHS [J].

SCHEINERMAN, ER .

DISCRETE MATHEMATICS, 1990, 82 (01) :105-109

[8] AN IMPROVED EDGE BOUND ON THE INTERVAL NUMBER OF A GRAPH [J].

SPINRAD, JR ;

VIJAYAN, G ;

WEST, DB .

JOURNAL OF GRAPH THEORY, 1987, 11 (03) :447-449

← 1 →