How to make a graph bipartite

DOI10.1016/0095-8956(88)90057-3MaRDI QIDQ805628zbMATH OpenOpenAlexWikidataFDO

Authors János Pach, Ralph Faudree, Joel Spencer, P. Erdős

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)

Recommendations

• scientific article; zbMATH DE number 426334
• scientific article; zbMATH DE number 850231
• Bipartite subgraphs
• For which densities are random triangle-free graphs almost surely bipartite?
• Making a K₄-free graph bipartite

Cites work

• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 4029614 (Why is no real title available?)
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 3482343 (Why is no real title available?)
• scientific article; zbMATH DE number 3487496 (Why is no real title available?)
• scientific article; zbMATH DE number 3307332 (Why is no real title available?)
• scientific article; zbMATH DE number 3333194 (Why is no real title available?)
• A dense infinite Sidon sequence
• Asymptotic lower bounds for Ramsey functions
• Graph Theory and Probability. II
• Graph theory with applications
• More results on Ramsey-Turán type problems
• On circuits and subgraphs of chromatic graphs
• On some extremal problems in graph theory

Cited in

(33)

• extremal aspects of the Erdős-Gallai-Tuza conjecture
• The Spectrum of Triangle-Free Graphs
• The clique number and the smallest \(Q\)-eigenvalue of graphs
• scientific article; zbMATH DE number 426334 (Why is no real title available?)
• Problems and results on judicious partitions
• On a Conjecture of Erdős, Gallai, and Tuza
• A note on bipartite subgraphs and triangle-independent sets
• On triangle-free graphs maximizing embeddings of bipartite graphs
• Dense induced bipartite subgraphs in triangle-free graphs
• On the edge distribution of a graph
• Sparse halves in triangle-free graphs
• Making a K₄-free graph bipartite
• Pentagons vs. triangles
• On the minimum degree forcing \(F\)-free graphs to be (nearly) bipartite
• On set systems with a threshold property
• The local density of triangle-free graphs
• Judicious partitions of hypergraphs
• More about sparse halves in triangle-free graphs
• Books versus triangles at the extremal density
• 10 problems for partitions of triangle-free graphs
• On the power of random greedy algorithms
• Linear-Time Approximation Algorithms for the Max Cut Problem
• A note on bipartite subgraphs of triangle‐free graphs
• Judicious partitions of graphs
• Cycle-maximal triangle-free graphs
• SOME OF MY FAVORITE SOLVED AND UNSOLVED PROBLEMS IN GRAPH THEORY
• Judicious partitions of 3-uniform hypergraphs
• Bounds on Ramsey games via alterations
• Lower bounds for max-cut in \(H\)-free graphs via semidefinite programming
• Exact stability for Turán's theorem
• scientific article; zbMATH DE number 841651 (Why is no real title available?)
• Sparse halves in K4‐free graphs
• Making K_r+1-free graphs r-partite

This page was built for publication: How to make a graph bipartite

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