How to make a graph bipartite

DOI10.1016/0095-8956(88)90057-3zbMath0729.05025OpenAlexW2989103922WikidataQ105709587 ScholiaQ105709587MaRDI QIDQ805628

Paul Erdős, János Pach, Ralph J. Faudree, J. H. Spencer

Publication date: 1988

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0095-8956(88)90057-3

zbMATH Keywords

bipartitetriangle-free graphforbidden graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (05C99)

Related Items

The clique number and the smallest \(Q\)-eigenvalue of graphs, Making K_r+1-free graphs r-partite, Problems and results on judicious partitions, A note on bipartite subgraphs and triangle-independent sets, On the power of random greedy algorithms, Judicious partitions of hypergraphs, A note on bipartite subgraphs of triangle‐free graphs, On set systems with a threshold property, SOME OF MY FAVORITE SOLVED AND UNSOLVED PROBLEMS IN GRAPH THEORY, Linear-Time Approximation Algorithms for the Max Cut Problem, The local density of triangle-free graphs, On a Conjecture of Erdős, Gallai, and Tuza, Sparse halves in K4‐free graphs, Bounds on Ramsey games via alterations, The Spectrum of Triangle-Free Graphs, Cycle-maximal triangle-free graphs, Judicious partitions of 3-uniform hypergraphs, Pentagons vs. triangles, Making a \(K_4\)-free graph bipartite, Dense induced bipartite subgraphs in triangle-free graphs, Sparse halves in triangle-free graphs, Books versus Triangles at the Extremal Density, More about sparse halves in triangle-free graphs, Lower Bounds for Max-Cut in $H$-Free Graphs via Semidefinite Programming, extremal aspects of the Erdős-Gallai-Tuza conjecture, Judicious partitions of graphs, Exact stability for Turán’s Theorem

Cites Work

• More results on Ramsey-Turán type problems
• A dense infinite Sidon sequence
• Asymptotic lower bounds for Ramsey functions
• On some extremal problems in graph theory
• Graph Theory and Probability. II
• On circuits and subgraphs of chromatic graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item