Making a \(K_4\)-free graph bipartite

DOI10.1007/s00493-007-2238-0zbMath1164.05035arXiv0706.4101OpenAlexW2087280368MaRDI QIDQ950329

Benjamin Sudakov

Publication date: 22 October 2008

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0706.4101

zbMATH Keywords

bipartite graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Related Items

The clique number and the smallest \(Q\)-eigenvalue of graphs ⋮ Making K_r+1-free graphs r-partite ⋮ A note on bipartite subgraphs and triangle-independent sets ⋮ Sparse halves in K4‐free graphs ⋮ Making an H $H$‐free graph k $k$‐colorable ⋮ Dense induced bipartite subgraphs in triangle-free graphs ⋮ Sparse halves in triangle-free graphs ⋮ Lower Bounds for Max-Cut in $H$-Free Graphs via Semidefinite Programming ⋮ Exact stability for Turán’s Theorem

Cites Work

• How to make a graph bipartite
• Maximum cuts and judicious partitions in graphs without short cycles
• On the edge distribution in triangle-free graphs
• Sparse halves in triangle-free graphs
• Bipartite subgraphs
• Largest bipartite subgraphs in triangle-free graphs with maximum degree three
• A note on bipartite subgraphs of triangle‐free graphs
• Local Density in Graphs with Forbidden Subgraphs
• Some Extremal Properties of Bipartite Subgraphs
• MaxCut in ${\bm H)$-Free Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item