𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Bipartite subgraphs of integer weighted graphs

✍ Scribed by Noga Alon; Eran Halperin

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
411 KB
Volume
181
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

For every integer p > 0, let f(p) be the minimum possible value of the maximum weight of a cut in an integer weighted graph with total weight p. It is shown that for every large n and every m < n, f((~)+m)= L¼n2j +min (I½nT,f(m)). This supplies the precise value of f(p) for many values of p including, e.g., all p = (i) ÷ (~) when n is large enough and ~ml 2 ~< 5n.

📜 SIMILAR VOLUMES

On Ramsey graphs without bipartite subgr
On Ramsey graphs without bipartite subgraphs
✍ Jaroslav Nešetřil; Vojtěch Rödl 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 388 KB

NeSetfil, J. and V. Riidl, On Ramsey graphs without bipartite subgraphs, Discrete Mathematics 101 (1992) 223-229. We prove that for every graph H without triangles and K,,,,,m, n G 2, there exists a Ramsey graph with the same properties. This answers a problem due to Erd& and Faudree. Moreover we

Extremal bipartite subgraphs of cubic tr
Extremal bipartite subgraphs of cubic triangle-free graphs
✍ Glenn Hopkins; William Staton 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 275 KB

## Abstract A cubic triangle‐free graph has a bipartite subgraph with at least 4/5 of the original edges. Examples show that this is a best possible result.

Turán problems for integer-weighted grap
Turán problems for integer-weighted graphs
✍ Zoltán Füredi; André Kündgen 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 238 KB

## Abstract A multigraph is (__k__,__r__)‐dense if every __k__‐set spans at most __r__ edges. What is the maximum number of edges ex~ℕ~(__n__,__k__,__r__) in a (__k__,__r__)‐dense multigraph on __n__ vertices? We determine the maximum possible weight of such graphs for almost all __k__ and __r__ (e

A note on bipartite subgraphs of triangl
A note on bipartite subgraphs of triangle-free regular graphs
✍ S. C. Locke 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 130 KB 👁 2 views

## Abstract Lower bounds on the size of a maximum bipartite subgraph of a triangle‐free __r__‐regular graph are presented.