𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On maximum bipartite subgraphs

✍ Scribed by Günther Malle

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

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In this paper are investigated maximum bipartite subgraphs of graphs, i.e., bipartite subgraphs with a maximum number of edges. Such subgraphs are characterized and a criterion is given for a subgraph to be a unique maximum bipartite subgraph of a given graph. In particular maximum bipartite subgraphs of cubic graphs are investigated. It is shown that cubic graphs can be built up from five building stones (called elementary paths). Finally the investigation of a special class of cubic graphs yields a theorem which characterizes the Petersen graph and the dodecahedron graph by means of their maximum bipartite subgraphs.

📜 SIMILAR VOLUMES

Maximum k-colorable subgraphs
Maximum k-colorable subgraphs
✍ S. C. Locke 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 303 KB

## Abstract A lower bound is established on the number of edges in a maximum __k__‐colorable subgraph of a loopless graph __G__. For the special case of 3‐regular graphs, lower bounds are also determined on the maximum number of edges in a bipartite subgraph whose color classes are of equal size.

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

Bipartite induced subgraphs and well-qua
Bipartite induced subgraphs and well-quasi-ordering
✍ Nicholas Korpelainen; Vadim V. Lozin 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 238 KB

We study bipartite graphs partially ordered by the induced subgraph relation. Our goal is to distinguish classes of bipartite graphs that are or are not well-quasi-ordered (wqo) by this relation. Answering an open question from [J Graph Theory 16 (1992), 489-502], we prove that P 7 -free bipartite g

On 2-Connected Spanning Subgraphs with L
On 2-Connected Spanning Subgraphs with Low Maximum Degree
✍ Daniel P Sanders; Yue Zhao 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 408 KB

Given a graph G, let a k-trestle of G be a 2-connected spanning subgraph of G of maximum degree at most k. Also, let /(G) be the Euler characteristic of G. This paper shows that every 3-connected graph G has a (10&2/(G))-trestle. If /(G) &5, this is improved to 8&2/(G), and for /(G) &10, this is fur

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.