On a bipartition problem of Bollobás and Scott
type: Item
instance of: scholarly article
title: On a bipartition problem of Bollobás and Scott
zbMATH Open document ID: 1224.05255
author: Baogang Xu
author: Xingxing Yu
published in: Combinatorica
publication date: 2011-02-08T00:00:00Z
review text: The bipartite density of a graph \(G\) is \(\max\{| E(H)| /| E(G)|\, :\,H\) is a bipartite subgraph of \(G\}\). Let \(\mathcal H\) denote the collection of all connected cubic graphs which have bipartite density \(\frac 45\) and contain a maximum bipartite subgraph such that one of its partite sets is independent in \(G\). In the paper, it is proved that any graph in \(\mathcal H\) can be reduced, through a sequence of three types of operations, to a member of a well characterized class. As a consequence, an algorithm which decides whether a given graph belongs to \(\mathcal H\) is given.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 5848530
zbMATH Keywords: bipartite graph
zbMATH Keywords: bipartite density
zbMATH Keywords: biased maximum bipartite subgraph
MaRDI profile type: Publication
full work available at URL: s00493-009-2381-x
OpenAlex ID: W1981723335
cites work: Exact bounds for judicious partitions of graphs
cites work: Problems and results on judicious partitions
cites work: Largest bipartite subgraphs in triangle-free graphs with maximum degree three
cites work: Some Extremal Properties of Bipartite Subgraphs
cites work: Q4090369
cites work: Extremal bipartite subgraphs of cubic triangle-free graphs
cites work: On maximum bipartite subgraphs
cites work: Q4304355
cites work: Triangle-free subcubic graphs with minimum bipartite density
cites work: Node-and edge-deletion NP-complete problems
DOI: 10.1007/S00493-009-2381-X
Recommended article: On several partitioning problems of Bollobás and Scott
Recommended article: On a bottleneck bipartition conjecture of Erdős
Recommended article: The P k Partition Problem and Related Problems in Bipartite Graphs
Recommended article: The solution of the bipartite analogue of the Oberwolfach problem
Recommended article: On the bipartition of graphs
Recommended article: Q4848415
Recommended article: On separating families of bipartitions
Recommended article: Combinatorial proof of a partition inequality of Bessenrodt-Ono
Recommended article: On two partition problems
Recommended article: Partitions with part difference conditions and Bressoud's conjecture
description: scientific article; zbMATH DE number 5848530