A note on dense bipartite induced subgraphs

2020/06/09 by Stefan Glock, Glock, Stefan · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2006.05101

openalex publication_date 2020/06/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This exposition contains a short and streamlined proof of the recent result of Kwan, Letzter, Sudakov and Tran that every triangle-free graph with minimum degree d contains an induced bipartite subgraph with average degree Ω(ln d/lnln d).

Cited by

• C₄-free subgraphs of high degree with geometric applications

Related

• Dense induced bipartite subgraphs in triangle-free graphs
• Dense induced subgraphs of dense bipartite graphs
• Bipartite induced density in triangle-free graphs
• Every graph contains a linearly sized induced subgraph with all degrees odd
• On the structure of dense graphs with fixed clique number