How to make a graph bipartite

DOI10.1016/0095-8956(88)90057-3zbMATH Open0729.05025OpenAlexW2989103922WikidataQ105709587 ScholiaQ105709587MaRDI QIDQ805628FDOQ805628

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

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_4\)-free graph bipartite

zbMATH Keywords

bipartitetriangle-free graphforbidden graph

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Graph theory with applications
• Title not available (Why is that?)
• On some extremal problems in graph theory
• Asymptotic lower bounds for Ramsey functions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graph Theory and Probability. II
• Title not available (Why is that?)
• More results on Ramsey-Turán type problems
• A dense infinite Sidon sequence
• On circuits and subgraphs of chromatic graphs
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (33)

• The Spectrum of Triangle-Free Graphs
• extremal aspects of the Erdős-Gallai-Tuza conjecture
• Title not available (Why is that?)
• Problems and results on judicious partitions
• The clique number and the smallest \(Q\)-eigenvalue of graphs
• On a Conjecture of Erdős, Gallai, and Tuza
• On triangle-free graphs maximizing embeddings of bipartite graphs
• A note on bipartite subgraphs and triangle-independent sets
• On the edge distribution of a graph
• Dense induced bipartite subgraphs in triangle-free graphs
• Sparse halves in triangle-free graphs
• Making a \(K_4\)-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
• Judicious partitions of graphs
• A note on bipartite subgraphs of triangle‐free 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
• Title not available (Why is that?)
• 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)