✦ LIBER ✦

A note on maximal triangle-free graphs

✍ Scribed by Wayne Goddard; Daniel J. Kleitman

Publisher: John Wiley and Sons
Year: 1993
Tongue: English
Weight: 150 KB
Volume: 17
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190170510

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We show that a maximal triangle‐free graph on n vertices with minimum degree δ contains an independent set of 3δ − n vertices which have identical neighborhoods. This yields a simple proof that if the binding number of a graph is at least 3/2 then it has a triangle. This was conjectured originally by Woodall. © 1993 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

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.

A note on the matching numbers of triang

A note on the matching numbers of triangle-free graphs

✍ Roberto W. Frucht; Reinaldo E. Giudici 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 137 KB 👁 1 views

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

A note on triangle-free quasi-symmetric

A note on triangle-free quasi-symmetric designs

✍ Rajendra M. Pawale 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 84 KB 👁 1 views

Triangle-free quasi-symmetric 2-(v, k,k) designs with intersection numbers x, y; 01, are investigated. It is proved that k ≥ 2 yx -3. As a consequence it is seen that for fixed k, there are finitely many triangle-free quasi-symmetric designs. It is also proved that: k ≤ y( yx)+ x.

On minimal 5-chromatic triangle-free gra

On minimal 5-chromatic triangle-free graphs

✍ David Avis 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 139 KB 👁 1 views

## Abstract It is shown that the minimum number of vertices in a triangle‐free 5‐chromatic graph is at least 19.

Spin Models on Triangle-Free Connected G

Spin Models on Triangle-Free Connected Graphs

✍ Kazumasa Nomura 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 388 KB

Spin models were introduced by V. Jones (Pac. J. Math. 137 (1989), 311 334) to construct invariants of knots and links. A spin model is defined as a pair S=(X, w) of a fine set X and a function w: X\_X Ä C satisfying several axioms. Let 1=(X, E) be a connected graph with the usual metric : X\_X Ä [0