𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On a Conjecture of Rödl and Voigt

✍ Scribed by P. Komjath; E.C. Milner

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
408 KB
Volume
61
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

We prove that if (\lambda) is an infinite cardinal number and (G) is any graph of cardinality (\kappa=\lambda^{+})which is a union of a finite number of forests, then there is a graph (H_{k}) of size (\kappa) (which does not depend upon (G) ) so that (H_{k} \rightarrow(G){k}^{1}). Rödl and Voight conjectured that there is such a graph (H{\kappa}) for the special case when (G) is the regular tree on (\kappa) in which every vertex has degree (\kappa). We also prove that if a graph is the union of (n) forests, then it has colouring number (2 n). 1994 Academic Press. Inc.

📜 SIMILAR VOLUMES

A linear programming perspective on the
A linear programming perspective on the Frankl—Rödl—Pippenger theorem
✍ Jeff Kahn 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 394 KB 👁 1 views

For X a hypergraph on vertex set V and t : X+ R+, set We give a simple proof, based on an argument of Pippenger and Spencer [19] of the following rather general statement. Theorem 1.5. Fix k and 1. Let X be a k-bounded hypergraph and t a fractional matching of X. Let, furthermore, c , , . . . , c,

On a conjecture of Thomassen concerning
On a conjecture of Thomassen concerning subgraphs of large girth
✍ Domingos Dellamonica Jr; Václav Koubek; Daniel M. Martin; Vojtěch Rödl 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 156 KB

In 1983 C. Thomassen conjectured that for every k, g ∈ N there exists d such that any graph with average degree at least d contains a subgraph with average degree at least k and girth at least g. Kühn and Osthus [2004] proved the case g = 6. We give another proof for the case g = 6 which is based

On a Conjecture Concerning a Theorem of
On a Conjecture Concerning a Theorem of Cramér and Wold
✍ Guenther Walther 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 302 KB

A conjecture concerning the Crame r Wold device is answered in the negative by giving a Fourier-free, probabilistic proof using only elementary techniques. It is also shown how a geometric idea allows one to interpret the Crame r Wold device as a special case of a more general concept.

On a conjecture of Thomassen and Toft
On a conjecture of Thomassen and Toft
✍ Kriesell, Matthias 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 183 KB 👁 2 views

This article is motivated by a conjecture of Thomassen and Toft on the number s 2 (G) of separating vertex sets of cardinality 2 and the number v 2 (G) of vertices of degree 2 in a graph G belonging to the class G of all 2-connected graphs without nonseparating induced cycles. Let G denote the numbe

On a conjecture of wang and williams
On a conjecture of wang and williams
✍ N. V. R. Mahadev; Uri N. Peled 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 210 KB

## Abstract Wang and Williams defined a __threshold assignment__ for a graph __G__ as an assignment of a non‐negative weight to each vertex and edge of __G__, and a threshold __t__, such that a set __S__ of vertices is stable if and only if the total weight of the subgraph induced by __S__ does not