Triangle-free subcubic graphs with minimum bipartite density
A graph is subcubic if no degree exceeds 3. The bipartite density of a graph \(G\) is the maximum proportion of all edges of \(G\) contained in a bipartite subgraph of \(G\). Theorem 1.2 contains a proof of the conjecture of [\textit{J. A. Bondy} and \textit{S. C. Locke}, ``Largest bipartite subgraphs in triangle-free graphs with maximum degree three, J. Graph Theory 10, 477--504 (1986; Zbl 0609.05046)] that there are precisely 7 triangle-free subcubic graphs having bipartite density exactly equal to \(\frac45\). The authors announce that this result will be applied in a forthcoming paper which will solve a problem posed in [\textit{B. Bollobás} and \textit{A. D. Scott}, ``Problems and results on judicious partitions, Random Struct.\ Algorithms 21, No. 3--4, 414--430 (2002; Zbl 1013.05059)].
- Extremal bipartite subgraphs of cubic triangle-free graphs
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- scientific article; zbMATH DE number 3706475 (Why is no real title available?)
- scientific article; zbMATH DE number 3715594 (Why is no real title available?)
- scientific article; zbMATH DE number 3571502 (Why is no real title available?)
- scientific article; zbMATH DE number 3390827 (Why is no real title available?)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Improved approximation of Max-Cut on graphs of bounded degree
- Largest bipartite subgraphs in triangle-free graphs with maximum degree three
- Maximumk-colorable subgraphs
- Node-and edge-deletion NP-complete problems
- Problems and results on judicious partitions
- Some simplified NP-complete graph problems
- Maximum bipartite subgraphs of cubic triangle-free planar graphs
- Bipartite density of triangle-free subcubic graphs
- Bipartite density of cubic graphs
- Maximum directed cuts in graphs with degree constraints
- New formulae for the bipartite vertex frustration and decycling number of graphs
- Maximum bisections of graphs without cycles of length 4
- On judicious bipartitions of directed graphs
- Maximum bisections of graphs without short even cycles
- A bound on judicious bipartitions of directed graphs
- On bisections of directed graphs
- Bipartite subgraphs of triangle-free subcubic graphs
- On judicious partitions of uniform hypergraphs
- Bounds for pairs in judicious partitioning of graphs
- Maximum directed cuts in digraphs with degree restriction
- A note on bipartite subgraphs of triangle‐free graphs
- Bipartite Subgraphs of Triangle-Free Graphs
- Bisections of graphs without short cycles
- Maximum cuts of graphs with forbidden cycles
- A bound for judicious \(k\)-partitions of graphs
- On a problem of judicious k-partitions of graphs
- Judicious partitioning of hypergraphs with edges of size at most 2
- On maximum edge cuts of connected digraphs
- Partitioning digraphs with outdegree at least 4
- Graph partitioning: an updated survey
- On a bipartition problem of Bollobás and Scott
- On min-bisections of graphs
- On ratio-k-cuts of graphs
- On maximum bisections of \(\{C_4, \theta (2, 3, 3)\}\)-free graphs
- Lower bounds for maximum weight bisections of weighted triangle-free subcubic graphs
This page was built for publication: Triangle-free subcubic graphs with minimum bipartite density
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2483477)
