Max k-cut and judicious k-partitions

被引：16

作者：

Bollobas, Bela ^{[2
,3
]}

Scott, Alex ^{[1
]}

机构：

[1] Math Inst, Oxford OX1 3LB, England

[2] Univ Cambridge, Dept Pure Math & Math Stat, Cambridge CB3 0WB, England

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

来源：

DISCRETE MATHEMATICS | 2010年 / 310卷 / 15-16期

基金：

美国国家科学基金会;

关键词：

Max cut; Judicious partitions; Extremal graph theory; BIPARTITE SUBGRAPHS; GRAPHS; HYPERGRAPHS; BOUNDS;

D O I：

10.1016/j.disc.2010.04.004

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Alon, et al. (2003) [1] proved that every graph with a large cut has a bipartition in which each vertex class contains correspondingly few edges. We prove an analogous result for partitions into k >= 3 classes; along the way we prove a result for biased bipartitions. (C) 2010 Elsevier B.V. All rights reserved.

引用

页码：2126 / 2139

页数：14

共 16 条

[1] Maximum cuts and judicious partitions in graphs without short cycles [J].

Alon, N ;

Bollobás, B ;

Krivelevich, M ;

Sudakov, B .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2003, 88 (02) :329-346

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

Alon, N ;

Halperin, E .

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

[3] Bipartite subgraphs [J].

Alon, N .

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

[4]

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

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

Bollobás, B ;

Scott, AD .

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

[6] Judicious partitions of hypergraphs [J].

Bollobas, B ;

Scott, AD .

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

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

Bollobás, B ;

Scott, AD .

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

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

Bollobás, B ;

Scott, AD .

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

[9]

BOLLOBAS B, 1993, PERIOD MATH HUNG, V26, P125

[10]

Edwards C. S., 1975, RECENT ADV GRAPH THE, P167

← 1 2 →