Some Extremal Properties of Bipartite Subgraphs

1973/06/01 by C. S. Edwards · 17 citations
Engineering · Mathematics · Computer Science · #graph theory and CDMA systems #Limits and Structures in Graph Theory #Graph Labeling and Dimension Problems

paper · pdf · doi:10.4153/cjm-1973-048-x

Abstract

G p = (V, X) is a graph on p vertices, with vertex set V and edge set X. Occasionally, to avoid ambiguity, V and X will be written V(G P ) and X(G P ), respectively.

Cited by

• New results for MaxCut in HH‐free graphs
• Maximizing several cuts simultaneously
• Frustration indices of signed subcubic graphs
• Nearly tight bounds for MaxCut in hypergraphs
• Bisections of Graphs Without Short Cycles
• New results for MaxCut in H-free graphs
• Making an H-Free Graph k-Colorable
• Tight bounds for judicious 3-partitions of graphs
• Structural properties of bipartite subgraphs
• From small eigenvalues to large cuts, and Chowla's cosine problem
• Bipartite Subgraphs of Triangle-Free Graphs
• Balanced Judicious Partition is Fixed-Parameter Tractable
• Beyond the MaxCut problem in H-free graphs
• Hypergraph cuts above the average
• Problems and results on judicious partitions
• Dense induced bipartite subgraphs in triangle-free graphs
• An Alon-Boppana--type bound for very dense graphs, with applications to max-cut

Related

• A note on "Extremal graphs with bounded vertex bipartiteness number"
• The history of degenerate (bipartite) extremal graph problems
• Generating p-extremal graphs
• Extremal numbers of disjoint triangles in r-partite graphs
• Extremal aspects of graph and hypergraph decomposition problems