𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the asymptotic structure of sparse triangle free graphs

✍ Scribed by Pr�mel, Hans J�rgen; Steger, Angelika

Publisher
John Wiley and Sons
Year
1996
Tongue
English
Weight
567 KB
Volume
21
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

An important result of Erdos, Kleitman, and Rothschild says that almost every triangle-free graph on n vertices has chromatic number 2. In this paper w e study the asymptotic structure of graphs in y0rb,,,(K3), i.e., in the class of trianglefree graphs on n vertices having rn = rn(n) edges. In particular w e prove that an analogue to the Erdos-Kleitman-Rothschild result is true, whenever rn P log n for some constant c > 0. On the other hand, it is shown that almost every graph in y0h,,,(K3) has at least chromatic number 3, provided that cln < rn < c2n312, where cl, c2 > 0 are appropriate constants.

📜 SIMILAR VOLUMES

The number of connected sparsely edged g
The number of connected sparsely edged graphs. III. Asymptotic results
✍ E. M. Wright 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 413 KB

## Abstract The number of connected graphs on __n__ labeled points and __q__ lines (no loops, no multiple lines) is __f(n,q).__ In the first paper of this series I showed how to find an (increasingly complicated) exact formula for __f(n,n+k)__ for general __n__ and successive __k.__ The method woul

On decomposition of triangle-free graphs
On decomposition of triangle-free graphs under degree constraints
✍ Kaneko, Atsushi 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 80 KB 👁 2 views

We prove that if s and t are positive integers and if G is a triangle-free graph with minimum degree s + t, then the vertex set of G has a decomposition into two sets which induce subgraphs of minimum degree at least s and t, respectively.

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.

On the asymptotic value of the choice nu
On the asymptotic value of the choice number of complete multi-partite graphs
✍ Nurit Gazit; Michael Krivelevich 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB 👁 1 views

## Abstract We calculate the asymptotic value of the choice number of complete multi‐partite graphs, given certain limitations on the relation between the sizes of the different sides. In the bipartite case, we prove that if __n__~0~ ≤ __n__~1~ and log__n__~0~ ≫ loglog__n__~1~, then $ch(K\_{n\_{0},