Judicious partitions of bounded‐degree graphs

DOI10.1002/jgt.10174zbMath1048.05067OpenAlexW2530638378MaRDI QIDQ4474279

Béla Bollobás, Alexander D. Scott

Publication date: 4 August 2004

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.10174

zbMATH Keywords

extremal graphsvertex partitionbounded-degree graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (18)

Judicious partitions of weighted hypergraphs ⋮ Problems and results on judicious partitions ⋮ Simultaneous Approximation of Constraint Satisfaction Problems ⋮ On bisections of graphs without complete bipartite graphs ⋮ On judicious bisections of graphs ⋮ Upper bounds on minimum balanced bipartitions ⋮ Graph partitioning: an updated survey ⋮ Optimal bisections of directed graphs ⋮ Defective coloring of hypergraphs ⋮ Bisections of graphs ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ Bounds for judicious balanced bipartitions of graphs ⋮ A note on balanced bipartitions ⋮ An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance ⋮ On judicious bipartitions of graphs ⋮ Bipartition of graph under degree constraints ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ On bisections of directed graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On a bottleneck bipartition conjecture of Erdős
• Maximum cuts: Improvements and local algorithmic analogues of the Edwards-Erdős inequality
• Judicious partitions of hypergraphs
• Bipartite subgraphs of integer weighted graphs
• Judicious partitions of 3-uniform hypergraphs
• Exact bounds for judicious partitions of graphs
• Largest bipartite subgraphs in triangle-free graphs with maximum degree three
• Maximumk-colorable subgraphs
• Extremal bipartite subgraphs of cubic triangle-free graphs
• Problems and results on judicious partitions
• Some Extremal Properties of Bipartite Subgraphs

This page was built for publication: Judicious partitions of bounded‐degree graphs