Triangle-free subcubic graphs with minimum bipartite density

DOI10.1016/J.JCTB.2007.09.001MaRDI QIDQ2483477zbMATH OpenOpenAlexFDO

Authors Xingxing Yu, Baogang 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

subcubic graphtriangle-free graphbipartite densitybipartite subgraph

Mathematics Subject Classification ID

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

Recommendations

• Bipartite density of triangle-free subcubic graphs
• Bipartite subgraphs of triangle-free subcubic graphs
• Bipartite density of cubic graphs
• Maximum bipartite subgraphs of cubic triangle-free planar graphs
• On a bipartition problem of Bollobás and Scott

Cites work

• 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?)
• 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
• 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

Cited in

(25)

• Maximum bisections of graphs without short even cycles
• On judicious partitions of uniform hypergraphs
• A bound for judicious \(k\)-partitions of graphs
• New formulae for the bipartite vertex frustration and decycling number of graphs
• Maximum directed cuts in digraphs with degree restriction
• Bipartite Subgraphs of Triangle-Free Graphs
• Bipartite density of triangle-free subcubic graphs
• Graph partitioning: an updated survey
• Maximum cuts of graphs with forbidden cycles
• Maximum bisections of graphs without cycles of length 4
• A bound on judicious bipartitions of directed graphs
• Maximum bipartite subgraphs of cubic triangle-free planar graphs
• A note on bipartite subgraphs of triangle‐free graphs
• Bisections of graphs without short cycles
• Judicious partitioning of hypergraphs with edges of size at most 2
• On judicious bipartitions of directed graphs
• On maximum edge cuts of connected digraphs
• On bisections of directed graphs
• On a bipartition problem of Bollobás and Scott
• Partitioning digraphs with outdegree at least 4
• Bounds for pairs in judicious partitioning of graphs
• Maximum directed cuts in graphs with degree constraints
• Bipartite density of cubic graphs
• Bipartite subgraphs of triangle-free subcubic graphs
• On a problem of judicious \(k\)-partitions of 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)