Max-bisections of \(H\)-free graphs

DOI10.1016/j.disc.2019.07.006zbMath1429.05163OpenAlexW2956212118MaRDI QIDQ2279266

Juan Yan, Jian-Feng Hou

Publication date: 12 December 2019

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2019.07.006

zbMATH Keywords

cyclemax-bisection\((l, 4)\)-fan

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distance in graphs (05C12) Connectivity (05C40)

Related Items (4)

Maximum bisections of graphs without cycles of length 4 ⋮ On bisections of graphs without complete bipartite graphs ⋮ Graph partitioning: an updated survey ⋮ Maximum bisections of graphs without short even cycles

Cites Work

• Unnamed Item
• On judicious bisections of graphs
• Bisections of graphs
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• On tight components and anti-tight components
• The size of the largest bipartite subgraphs
• Bisections of graphs without \(K_{2, l}\)
• Cycles of even length in graphs
• .879-approximation algorithms for MAX CUT and MAX 2SAT
• Bipartite Subgraphs of Triangle-Free Graphs
• Gadgets, Approximation, and Linear Programming
• Bisections of Graphs Without Short Cycles
• Maximum cuts of graphs with forbidden cycles
• Some optimal inapproximability results
• Some Extremal Properties of Bipartite Subgraphs
• MaxCut in ${\bm H)$-Free Graphs

This page was built for publication: Max-bisections of \(H\)-free graphs