𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A note on bipartite subgraphs of triangle-free regular graphs

✍ Scribed by S. C. Locke

Publisher
John Wiley and Sons
Year
1990
Tongue
English
Weight
130 KB
Volume
14
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Lower bounds on the size of a maximum bipartite subgraph of a triangle‐free r‐regular graph are presented.

πŸ“œ SIMILAR VOLUMES

Extremal bipartite subgraphs of cubic tr
Extremal bipartite subgraphs of cubic triangle-free graphs
✍ Glenn Hopkins; William Staton πŸ“‚ Article πŸ“… 1982 πŸ› John Wiley and Sons 🌐 English βš– 275 KB

## Abstract A cubic triangle‐free graph has a bipartite subgraph with at least 4/5 of the original edges. Examples show that this is a best possible result.

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

On the number of maximal bipartite subgr
On the number of maximal bipartite subgraphs of a graph
✍ Jesper Makholm Byskov; Bolette AmmitzbΓΈll Madsen; Bjarke Skjernaa πŸ“‚ Article πŸ“… 2004 πŸ› John Wiley and Sons 🌐 English βš– 72 KB πŸ‘ 2 views

We show new lower and upper bounds on the maximum number of maximal induced bipartite subgraphs of graphs with n vertices. We present an infinite family of graphs having 105 n=10 % 1:5926 n ; such subgraphs show an upper bound of O(12 n=4 ) ΒΌ O(1:8613 n ) and give an algorithm that finds all maximal

A Note on Almost Regular Graphs
A Note on Almost Regular Graphs
✍ M. Of Hofmeister Munich πŸ“‚ Article πŸ“… 1994 πŸ› John Wiley and Sons 🌐 English βš– 136 KB

It can easily be seen that a conjecture of RUNGE does not hold for a class of graphs whose members will be called "almost regular". This conjecture is replaced by a weaker one, and a classification of almost regular graphs is given.