Judicious partitions of bounded-degree graphs

被引：25

作者：

Bollobás, B ^{[1
]}

Scott, AD

机构：

[1] Univ Cambridge Trinity Coll, Cambridge CB2 1TQ, England

[2] Univ Memphis, Dept Math Sci, Memphis, TN 38152 USA

[3] UCL, Dept Math, London WC1E 6BT, England

来源：

JOURNAL OF GRAPH THEORY | 2004年 / 46卷 / 02期

关键词：

D O I：

10.1002/jgt.10174

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We prove results on partitioning graphs G with bounded maximum degree. In particular, we provide optimal bounds for bipartitions V(G) = V(1) boolean OR V(2) in which we minimize max{e(V(1)), e(V(2))}. (C) 2004 Wiley Periodicals, Inc.

引用

页码：131 / 143

页数：13

共 20 条

[1] Bipartite subgraphs of integer weighted graphs [J].

Alon, N ;

Halperin, E .

DISCRETE MATHEMATICS, 1998, 181 (1-3) :19-29

[2] Bipartite subgraphs [J].

Alon, N .

COMBINATORICA, 1996, 16 (03) :301-311

[3]

Bollobás B, 2002, BOLYAI MATH STUD, V10, P185

[4] Problems and results on judicious partitions [J].

Bollobás, B ;

Scott, AD .

RANDOM STRUCTURES & ALGORITHMS, 2002, 21 (3-4) :414-430

[5] Judicious partitions of hypergraphs [J].

Bollobas, B ;

Scott, AD .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 1997, 78 (01) :15-31

[6] Exact bounds for judicious partitions of graphs [J].

Bollobás, B ;

Scott, AD .

COMBINATORICA, 1999, 19 (04) :473-486

[7] Judicious partitions of 3-uniform hypergraphs [J].

Bollobás, B ;

Scott, AD .

EUROPEAN JOURNAL OF COMBINATORICS, 2000, 21 (03) :289-300

[8]

Bollobas B., 1993, PERIOD MATH HUNG, V26, P127

[9] LARGEST BIPARTITE SUBGRAPHS IN TRIANGLE-FREE GRAPHS WITH MAXIMUM DEGREE 3 [J].

BONDY, JA ;

LOCKE, SC .

JOURNAL OF GRAPH THEORY, 1986, 10 (04) :477-504

[10] Maximum cuts: Improvements and local algorithmic analogues of the Edwards-Erdos inequality [J].

Bylka, S ;

Idzik, A ;

Tuza, Z .

DISCRETE MATHEMATICS, 1999, 194 (1-3) :39-58

← 1 2 →