Name
Abstract | ||
|---|---|---|
In a 1965 paper, Erdos remarked that a graph G has a bipartite subgraph that has at least half as many edges as G. The purpose of this note is to prove a matroid analogue of Erdos's original observation. It follows from this matroid result that every loopless binary matroid has a restriction that uses more than half of its elements and has no odd circuits; and, for 2@?k@?5, every bridgeless graph G has a subgraph that has a nowhere-zero k-flow and has more than k-1k|E(G)| edges. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.ejc.2011.04.005 | Eur. J. Comb. |
Keywords | Field | DocType |
bipartite restriction,binary matroids,matroid analogue,odd circuit,bipartite subgraph,bridgeless graph,matroid result,graph g,nowhere-zero k-flow,loopless binary matroid,original observation | Matroid,Pseudoforest,Discrete mathematics,Combinatorics,k-edge-connected graph,Bipartite graph,Matroid partitioning,Graphic matroid,Weighted matroid,Mathematics,Branch-decomposition | Journal |
Volume | Issue | ISSN |
32 | 8 | 0195-6698 |
Citations | PageRank | References |
0 | 0.34 | 4 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| James Oxley | 1 | 194 | 24.39 |