𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A note on the independence number of triangle-free graphs

✍ Scribed by James B. Shearer

Publisher
Elsevier Science
Year
1983
Tongue
English
Weight
188 KB
Volume
46
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

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

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.

On the independence number of random gra
On the independence number of random graphs
✍ A.M. Frieze πŸ“‚ Article πŸ“… 1990 πŸ› Elsevier Science 🌐 English βš– 239 KB

Let (Y(G~,~) denote the independence number of the random graph Gn,p. Let d = np. We show that if E > 0 is fixed then with probability going to 1 as n + m cu(G& -$t (log d -log log dlog 2 + 1) < 7 provided d, s d = o(n), where d, is some fixed constant.

On the independence number in K1, r+1-fr
On the independence number in K1, r+1-free graphs
✍ ZdenΔ›k RyjÑček; Ingo Schiermeyer πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 353 KB

In this paper we use the degree sequence, order, size and vertex connectivity of a K 1,,+ 1 -free graph or of an almost claw-free graph to obtain several upper bounds on its independence number. We also discuss the sharpness of these results.