✦ LIBER ✦

Toughness and Triangle-Free Graphs

✍ Scribed by D. Bauer; J. Vandenheuvel; E. Schmeichel

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 520 KB
Volume: 65
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1995.1051

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Triangle-free regular graphs

✍ A.F. Sidorenko 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 152 KB

On triangle-free random graphs

✍ Tomasz Łuczak 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 167 KB 👁 3 views

We show that for every k ≥ 1 and δ > 0 there exists a constant c > 0 such that, with probability tending to 1 as n → ∞, a graph chosen uniformly at random among all triangle-free graphs with n vertices and M ≥ cn 3/2 edges can be made bipartite by deleting δM edges. As an immediate consequence of th

Triangle-free four-chromatic graphs

✍ Guoping Jin 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 640 KB

For given n, let G be a triangle-free graph of order n with chromatic number at least 4. In this paper, we shall prove a conjecture of H/iggkvist by determining the maximal value of 6(G).

2-factors in triangle-free graphs

✍ Bauer, D.; van den Heuvel, J.; Schmeichel, E. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 440 KB 👁 3 views

We study the cycle structure of I-tough, triangle-free graphs. In particular, w e prove that every such graph on n 2 3 vertices with minimum degree 6 2 i ( n + 2) has a 2-factor. W e also show this is best possible by exhibiting an infinite class of I-tough, triangle-free graphs having 6 = $ ( n + 1

Graphs without large triangle free subgr

Graphs without large triangle free subgraphs

✍ B. Bollobás; H.R. Hind 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 751 KB

Bollobas, B. and H.R. Hind, Graphs without large triangle free subgraphs, Discrete Mathematics 87 (1991) 119-131. The main aim of the paper is to show that for 2 < r <s and large enough n, there are graphs of order n and clique number less than s in which every set of vertices, which is not too sma

Degree sequences in triangle-free graphs

✍ Paul Erdős; Siemion Fajtlowicz; William Staton 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 250 KB