✦ LIBER ✦

Large induced trees in sparse random graphs

✍ Scribed by A.M Frieze; B Jackson

Publisher: Elsevier Science
Year: 1987
Tongue: English
Weight: 621 KB
Volume: 42
Category: Article
ISSN: 0095-8956
DOI: 10.1016/0095-8956(87)90039-6

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On large induced trees and long induced

On large induced trees and long induced paths in sparse random graphs

✍ W.C.Stephen Suen 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 697 KB

Maximal induced trees in sparse random g

Maximal induced trees in sparse random graphs

✍ Tomasz łuczak; Zbigniew Palka 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 493 KB

A study of the orders of maximal induced trees in a random graph G, with small edge probability p is given. In particular, it is shown that the giant component of almost every G,, where p = c/n and c > 1 is a constant, contains only very small maximal trees (that are of a specific type) and very lar

Trees in sparse random graphs

✍ W.Fernandez de la Vega 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 471 KB

The largest induced tree in a sparse ran

The largest induced tree in a sparse random graph

✍ W. Fernandez de la Vega 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 192 KB 👁 2 views

The author proved that, for c > 1, the random graph G(n, p ) on n vertices with edge probability p = c / n contains almost always an induced tree on at least q n ( 1 -o( 1)) vertices, where L Y ~ is the positive root of the equation CLY = log( 1 + c'a). It is shown here that if c is sufficiently lar

Large induced forests in sparse graphs

✍ Noga Alon; Dhruv Mubayi; Robin Thomas 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 148 KB

## Abstract For a graph __G__, let __a__(__G__) denote the maximum size of a subset of vertices that induces a forest. Suppose that __G__ is connected with __n__ vertices, __e__ edges, and maximum degree Δ. Our results include: (a) if Δ ≤ 3, and __G__ ≠ __K__~4~, then __a__(__G__) ≥ __n__ − e/4 − 1

On-Line Coloring of Sparse Random Graphs

On-Line Coloring of Sparse Random Graphs and Random Trees

✍ Boris Pittel; Robert S. Weishaar 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 164 KB

The performance of the greedy coloring algorithm ''first fit'' on sparse random graphs G and on random trees is investigated. In each case, approximately n, c r n log log n colors are used, the exact number being concentrated almost surely on at 2 most two consecutive integers for a sparse random gr