𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the Density of Subgraphs in a Graph with Bounded Independence Number

✍ Scribed by Pavel Valtr

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
260 KB
Volume
73
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

Let _(n, m, k) be the largest number _ # [0, 1] such that any graph on n vertices with independence number at most m has a subgraph on k vertices with at lest _ } ( k 2 ) edges. Up to a constant multiplicative factor, we determine _(n, m, k) for all n, m, k. For log n m=k n, our result gives _(n, m, m)=3(log(nΓ‚m)Γ‚m), which was conjectured by Alon (Random Structures Algorithms 9 (1996), 271 278).

πŸ“œ SIMILAR VOLUMES

On the number of maximal bipartite subgr
On the number of maximal bipartite subgraphs of a graph
✍ Jesper Makholm Byskov; Bolette AmmitzbΓΈll Madsen; Bjarke Skjernaa πŸ“‚ Article πŸ“… 2004 πŸ› John Wiley and Sons 🌐 English βš– 72 KB πŸ‘ 2 views

We show new lower and upper bounds on the maximum number of maximal induced bipartite subgraphs of graphs with n vertices. We present an infinite family of graphs having 105 n=10 % 1:5926 n ; such subgraphs show an upper bound of O(12 n=4 ) ΒΌ O(1:8613 n ) and give an algorithm that finds all maximal

The minimum number of subgraphs in a gra
The minimum number of subgraphs in a graph and its complement
✍ Lane Clark πŸ“‚ Article πŸ“… 1992 πŸ› John Wiley and Sons 🌐 English βš– 265 KB πŸ‘ 2 views

## Abstract For a graphb __F__ without isolated vertices, let __M__(__F__; __n__) denote the minimum number of monochromatic copies of __F__ in any 2‐coloring of the edges of __K__~__n__~. Burr and Rosta conjectured that when __F__ has order __t__, size __u__, and __a__ automorphisms. Independent

On the Maximum Number of Independent Cyc
On the Maximum Number of Independent Cycles in a Bipartite Graph
✍ Hong Wang πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 404 KB

Let G=(V 1 , V 2 ; E ) be a bipartite graph with |V 1 |= |V 2 | =n 2k, where k is a positive integer. Suppose that the minimum degree of G is at least k+1. We show that if n>2k, then G contains k vertex-disjoint cycles. We also show that if n=2k, then G contains k&1 quadrilaterals and a path of orde