Dense induced bipartite subgraphs in triangle-free graphs

DOI10.1007/s00493-019-4086-0zbMath1463.05313arXiv1810.12144OpenAlexW2999995332WikidataQ126349588 ScholiaQ126349588MaRDI QIDQ2003768

Yanyan Li

Publication date: 2 October 2020

Published in: Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

triangle-free graphsinduced bipartite subgraphs

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Density (toughness, etc.) (05C42)

Related Items (10)

\(C_4\)-free subgraphs with large average degree ⋮ On the power of random greedy algorithms ⋮ Counterexamples to a Conjecture of Harris on Hall Ratio ⋮ Bipartite induced density in triangle-free graphs ⋮ Finding a shortest even hole in polynomial time ⋮ Bounds on Ramsey games via alterations ⋮ Box and Segment Intersection Graphs with Large Girth and Chromatic Number ⋮ Separation Choosability and Dense Bipartite Induced Subgraphs ⋮ Dense Induced Subgraphs of Dense Bipartite Graphs ⋮ Some Results on Chromatic Number as a Function of Triangle Count

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• How to make a graph bipartite
• Making a \(K_4\)-free graph bipartite
• Explicit Ramsey graphs and orthonormal labelings
• Maximum cuts and judicious partitions in graphs without short cycles
• Coloring triangle-free graphs with fixed size
• Coloring graphs with sparse neighborhoods
• The list chromatic number of graphs with small clique number
• Triangle-free graphs with large chromatic numbers
• Packing nearly optimal Ramsey \(R(3,t)\) graphs
• Bipartite induced density in triangle-free graphs
• Hypergraph cuts above the average
• On some extremal problems in graph theory
• Bipartite subgraphs
• Introduction to Random Graphs
• Some Results on Chromatic Number as a Function of Triangle Count
• Bipartite Subgraphs of Triangle-Free Graphs
• Bounding Ramsey numbers through large deviation inequalities
• Turán Numbers of Subdivided Graphs
• Separation Choosability and Dense Bipartite Induced Subgraphs
• Some Extremal Properties of Bipartite Subgraphs
• MaxCut in ${\bm H)$-Free Graphs

This page was built for publication: Dense induced bipartite subgraphs in triangle-free graphs