Bipartite subgraphs

被引：78

作者：

Alon, N ^{[1
]}

机构：

[1] TEL AVIV UNIV, RAYMOND & BEVERLY SACKLER FAC EXACT SCI, DEPT MATH, IL-69978 TEL AVIV, ISRAEL

来源：

COMBINATORICA | 1996年 / 16卷 / 03期

关键词：

D O I：

10.1007/BF01261315

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

It is shown that there exists a positive c so that for any large integer m, any graph with 2m(2) edges contains a bipartite subgraph with at least m(2)+m/2+c root m edges. This is tight up to the constant c and settles a problem of Erdos. It is also proved that any triangle-free graph with e>1 edges contains a bipartite subgraph with at least e/2+c'e(4/5) edges for some absolute positive constant c'. This is tight up to the constant c'.

引用

页码：301 / 311

页数：11

共 17 条

[1]

Alon N, 1994, ELECT J COMBINATORIC, V1

[2]

Alon N., 1992, PROBABILISTIC METHOD

[3]

Andersen L.D., 1983, ARS COMBINATORIA, V16, P259

[4]

EDWARDS CS, 1973, CAN J MATH, V25, P475, DOI 10.4153/CJM-1973-048-x

[5]

EDWARDS CS, 1975, P 2 CZECH S GRAPH TH, P167

[6]

Erdos P., 1979, Graph Theory and Related Topics, Proc. Conf. (Waterloo, ON, P153

[7]

Erdos P., 1995, P 26 SE INT C GRAPH

[8]

HOFMEISTER T, 1995, K PARTITE SUBGRAPHS

[9] TRIANGLE-FREE PARTIAL GRAPHS AND EDGE COVERING-THEOREMS [J].

LEHEL, J ;

TUZA, Z .

DISCRETE MATHEMATICS, 1982, 39 (01) :59-65

[10] MAXIMUM K-COLORABLE SUBGRAPHS [J].

LOCKE, SC .

JOURNAL OF GRAPH THEORY, 1982, 6 (02) :123-132

← 1 2 →