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.











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)