𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Extremal bipartite subgraphs of cubic triangle-free graphs

✍ Scribed by Glenn Hopkins; William Staton

Publisher
John Wiley and Sons
Year
1982
Tongue
English
Weight
275 KB
Volume
6
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Det-extremal cubic bipartite graphs
Det-extremal cubic bipartite graphs
✍ M. Funk; Bill Jackson; D. Labbate; J. Sheehan 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 132 KB

## Abstract Let __G__ be a connected __k__–regular bipartite graph with bipartition __V__(__G__) = __X__ ∪ __Y__ and adjacency matrix __A__. We say __G__ is det‐extremal if __per__ (__A__) = |__det__(A)|. Det–extremal __k__–regular bipartite graphs exist only for __k__ =  2 or 3. McCuaig has charac

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.

Interval coloring of (3,4)-biregular bip
Interval coloring of (3,4)-biregular bipartite graphs having large cubic subgraphs
✍ A. V. Pyatkin 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 80 KB

## Abstract An interval coloring of a graph is a proper edge coloring such that the set of used colors at every vertex is an interval of integers. Generally, it is an NP‐hard problem to decide whether a graph has an interval coloring or not. A bipartite graph __G__ = (__A__,__B__;__E__) is (α, β)‐b

Extremal graphs with bounded densities o
Extremal graphs with bounded densities of small subgraphs
✍ Griggs, Jerrold R.; Simonovits, Mikl�os; Thomas, George Rubin 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 373 KB 👁 1 views

Let Ex(n, k, µ) denote the maximum number of edges of an n-vertex graph in which every subgraph of k vertices has at most µ edges. Here we summarize some known results of the problem of determining Ex(n, k, µ), give simple proofs, and find some new estimates and extremal graphs. Besides proving new

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

Topological subgraphs of cubic graphs an
Topological subgraphs of cubic graphs and a theorem of dirac
✍ Richard Statman 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 339 KB

## Abstract The topological subgraph relation between cubic graphs is analyzed. The analysis is then applied to generalize a theorem of Dirac.