𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On minimal 5-chromatic triangle-free graphs

✍ Scribed by David Avis

Publisher
John Wiley and Sons
Year
1979
Tongue
English
Weight
139 KB
Volume
3
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

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

πŸ“œ SIMILAR VOLUMES

On triangle-free random graphs
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 maximal triangle-free graphs
A note on maximal triangle-free graphs
✍ Wayne Goddard; Daniel J. Kleitman πŸ“‚ Article πŸ“… 1993 πŸ› John Wiley and Sons 🌐 English βš– 150 KB πŸ‘ 1 views

## 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 con

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

On decomposition of triangle-free graphs
On decomposition of triangle-free graphs under degree constraints
✍ Kaneko, Atsushi πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 80 KB πŸ‘ 2 views

We prove that if s and t are positive integers and if G is a triangle-free graph with minimum degree s + t, then the vertex set of G has a decomposition into two sets which induce subgraphs of minimum degree at least s and t, respectively.

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.