Triangle-free subcubic graphs with minimum bipartite density

DOI10.1016/j.jctb.2007.09.001zbMath1154.05053OpenAlexW2026975675MaRDI QIDQ2483477

Xingxing Yu, Bao-Gang Xu

Publication date: 28 April 2008

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2007.09.001

zbMATH Keywords

triangle-free graphsubcubic graphbipartite densitybipartite subgraph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75)

Related Items (21)

On judicious partitions of uniform hypergraphs ⋮ Maximum bisections of graphs without cycles of length 4 ⋮ On judicious bipartitions of directed graphs ⋮ Maximum directed cuts in graphs with degree constraints ⋮ Bounds for pairs in judicious partitioning of graphs ⋮ Partitioning digraphs with outdegree at least 4 ⋮ Graph partitioning: an updated survey ⋮ On a bipartition problem of Bollobás and Scott ⋮ Bisections of Graphs Without Short Cycles ⋮ Judicious Partitioning of Hypergraphs with Edges of Size at Most 2 ⋮ Maximum cuts of graphs with forbidden cycles ⋮ A bound for judicious \(k\)-partitions of graphs ⋮ Maximum bisections of graphs without short even cycles ⋮ On Maximum Edge Cuts of Connected Digraphs ⋮ New formulae for the bipartite vertex frustration and decycling number of graphs ⋮ Bipartite subgraphs of triangle-free subcubic graphs ⋮ A bound on judicious bipartitions of directed graphs ⋮ Maximum directed cuts in digraphs with degree restriction ⋮ On a Problem of Judiciousk-Partitions of Graphs ⋮ Bipartite density of triangle-free subcubic graphs ⋮ On bisections of directed graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some simplified NP-complete graph problems
• Improved approximation of Max-Cut on graphs of bounded degree
• Largest bipartite subgraphs in triangle-free graphs with maximum degree three
• Maximumk-colorable subgraphs
• Extremal bipartite subgraphs of cubic triangle-free graphs
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Problems and results on judicious partitions
• Node-and edge-deletion NP-complete problems

This page was built for publication: Triangle-free subcubic graphs with minimum bipartite density