𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Cutting a graph into two dissimilar halves

✍ Scribed by Paul Erdós; Mark Goldberg; János Pach; Joel Spencer

Publisher
John Wiley and Sons
Year
1988
Tongue
English
Weight
357 KB
Volume
12
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Given a graph G and a subset S of the vertex set of G, the discrepancy of S is defined as the difference between the actual and expected numbers of the edges in the subgraph induced on S. We show that for every graph with n vertices and e edges, n < e < n ( n -1)/4, there is an n/2-element subset with the discrepancy of the order of magnitude of f i e . For graphs with fewer than n edges, w e calculate the asymptotics for the maximum guaranteed discrepancy of an n/2-element subset. We also introduce a new notion called "bipartite discrepancy" and discuss related results and open problems.

📜 SIMILAR VOLUMES

Packing two forests into a bipartite gra
Packing two forests into a bipartite graph
✍ Wang, Hong 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 292 KB 👁 3 views

For two integers a and b, we say that a bipartite graph G admits an ( a , b)-bipartition if G has a bipartition ( X , Y ) such that /XI = a and ( Y / = b. We say that two bipartite graphs G and H are compatible if, for some integers a and b, both G and H admit ( a , b)-bipartitions. In this note, w

Partitioning a graph into two isomorphic
Partitioning a graph into two isomorphic pieces
✍ Anthony Bonato; Richard Nowakowski 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 137 KB

## Abstract A simple graph __G__ has the neighbour‐closed‐co‐neighbour property, or ncc property, if for all vertices __x__ of __G__, the subgraph induced by the set of neighbours of __x__ is isomorphic to the subgraph induced by the set of non‐neighbours of __x__. We present characterizations of g

Packing two bipartite graphs into a comp
Packing two bipartite graphs into a complete bipartite graph
✍ Wang, Hong 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 131 KB 👁 3 views

For two integers a and b, we say that a bipartite graph G admits an (a, b)bipartition if G has a bipartition (X, Y ) such that |X| = a and |Y | = b. We say that two bipartite graphs G and H are compatible if, for some integers a and b, both G and H admit (a, b)-bipartitions. In this paper, we prove

Packing two copies of a sparse graph int
Packing two copies of a sparse graph into a graph with restrained maximum degree
✍ Hong Wang 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 132 KB

## Abstract We show that if a tree __T__ is not a star, then there is an embedding σ of __T__ in the complement of __T__ such that the maximum degree of __T__∪σ(__T__) is at most Δ(__T__)+2. We also show that if __G__ is a graph of order __n__ with __n__−1 edges, then with several exceptions, there