The size of the largest bipartite subgraphs

DOI10.1016/S0012-365X(97)00004-6zbMATH Open0888.05035OpenAlexW2002958365WikidataQ105815733 ScholiaQ105815733MaRDI QIDQ1377883FDOQ1377883

Authors: András Gyárfás, Yoshiharu Kohayakawa, P. Erdős 

Publication date: 13 May 1998

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

Full work available at URL: https://doi.org/10.1016/s0012-365x(97)00004-6

Recommendations

• The size of bipartite graphs with a given girth
• On the number of maximal bipartite subgraphs of a graph
• On a problem of a. kotzig concerning factorizations of 4‐regular graphs
• Sizes of graphs with induced subgraphs of large maximum degree
• scientific article; zbMATH DE number 4008428
• On the sizes of large subgraphs of the binomial random graph
• Largest bipartite subgraphs in triangle-free graphs with maximum degree three
• The extremal number of the subdivisions of the complete bipartite graph
• The sizes of maximal planar, outerplanar, and bipartite planar subgraphs
• Bipartite graphs of large clique-width

zbMATH Keywords

bipartite subgraph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Cites Work

• Some Extremal Properties of Bipartite Subgraphs
• On some extremal problems in graph theory
• On coloring graphs to maximize the proportion of multicolored k-edges
• Title not available (Why is that?)

Cited In (26)

• Maximum bisections of graphs without short even cycles
• Maximum bipartite subgraphs in $H$-free graphs
• Bipartite subgraphs of \(H\)-free graphs
• Large Complete Bipartite Subgraphs In Incidence Graphs Of Points And Hyperplanes
• Bisections of graphs without \(K_{2, l}\)
• Bisections of graphs
• On bipartitions of directed graphs with small semidegree
• Hypergraph cuts above the average
• On \(k\)-partite subgraphs
• Graph partitioning: an updated survey
• Maximum bisections of graphs without cycles of length 4
• Max-bisections of \(H\)-free graphs
• Towards the distribution of the size of a largest planar matching and largest planar subgraph in random bipartite graphs
• Approximating sparse quadratic programs
• Maximum cuts in graphs without wheels
• Title not available (Why is that?)
• Bisections of graphs without short cycles
• MAX-CUT BY EXCLUDING BIPARTITE SUBGRAPHS
• Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
• Judicious partitions of 3-uniform hypergraphs
• Maximum bisections of graphs with girth at least six
• Maximum bisections of graphs without cycles of length four and five
• On bipartite restrictions of binary matroids
• Long Local Searches for Maximal Bipartite Subgraphs
• Judicious partitions of directed graphs
• \textsc{Max-Cut} parameterized above the Edwards-Erdős bound

This page was built for publication: The size of the largest bipartite subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1377883)