scientific article; zbMATH DE number 4008428
From MaRDI portal
Publication:3758861
[For the entire collection see Zbl 0619.00006.] In a graph with n vertices and q edges, it is proved that the number of edges b in a maximum bipartite subgraph and the independence i are related by the inequality \(b\leq q+2i-n\). For a k-regular graph the bipartite density b/q and independence ratio i/n are shown to be related by \(\frac{i}{n}\geq (k(b/q)-k+2)/4.\) Several classes of graphs for which the first inequality is best possible are investigated.
Recommendations
Cited in
(12)- Maximum bipartite subgraphs of Kneser graphs
- Bipartite subgraphs of graphs with maximum degree three
- The size of the largest bipartite subgraphs
- Maximum \(H\)-index of bipartite network with some given parameters
- On the sizes of bi-k-maximal graphs
- A note on a Caro-Wei bound for the bipartite independence number in graphs
- On a product dimension of bipartite graphs
- scientific article; zbMATH DE number 4137820 (Why is no real title available?)
- scientific article; zbMATH DE number 4059441 (Why is no real title available?)
- Independent edges in bipartite graphs obtained from orientations of graphs
- Bipartite independence number in graphs with bounded maximum degree
- On a problem of Harary
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3758861)