𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On a conjecture of Thomassen concerning subgraphs of large girth

✍ Scribed by Domingos Dellamonica Jr; Václav Koubek; Daniel M. Martin; Vojtěch Rödl

Publisher
John Wiley and Sons
Year
2010
Tongue
English
Weight
156 KB
Volume
67
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 result of F üredi [1983] about hypergraphs. We also show that the analogous conjecture for directed graphs is true. ᭧ 2010 Wiley

📜 SIMILAR VOLUMES

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 Concerning Monotonicity
On a Conjecture Concerning Monotonicity of Zeros of Ultraspherical Polynomials
✍ Dimitar K. Dimitrov 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 235 KB

Let C \* n , n=0, 1, ..., \*>&1Â2 be the ultraspherical (Gegenbauer) polynomials, orthogonal on (&1, 1) with respect to the weight (1&x 2 ) \*&1Â2 . Denote by `n, k (\*), k=1, ..., [nÂ2] the positive zeros of C \* n enumerated in decreasing order. The problem of finding the ``extremal'' function f f

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.

Proof of a Conjecture of Mader, Erdös an
Proof of a Conjecture of Mader, Erdös and Hajnal on Topological Complete Subgraphs
✍ B. Bollobás; A. Thomason 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 89 KB

We show that every graph G of size at least 256 p 2 |G| contains a topological complete subgraph of order p. This slight improvement of a recent result of Komlós and Szemerédi proves a conjecture made by Mader and by Erdös and Hajnal.

On a Conjecture of Lovász Concerning Bri
On a Conjecture of Lovász Concerning Bricks: II. Bricks of Finite Characteristic
✍ Marcelo H. de Carvalho; Cláudio L. Lucchesi; U.S.R. Murty 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 271 KB

we established the validity of the main theorem (1.1) for solid bricks. Here, we establish the existence of suitable separating cuts in nonsolid bricks and prove the theorem by applying induction to cut-contractions with respect to such cuts.