Dense Induced Subgraphs of Dense Bipartite Graphs

DOI10.1137/20M1370744MaRDI QIDQ4986805zbMATH OpenOpenAlexFDO

Authors Rose McCarty

Publication date 28 April 2021

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

average-degreegirthinduced subgraphs

Mathematics Subject Classification ID

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

Abstract: We prove that every bipartite graph of sufficiently large average degree has either a $K_{t,t}$-subgraph or an induced subgraph of average degree at least $t$ and girth at least $6$. We conjecture that "$6$" can be replaced by "$k$", which strengthens a conjecture of Thomassen. In support of this conjecture, we show that it holds for regular graphs.

Recommendations

• Dense induced bipartite subgraphs in triangle-free graphs
• Dense bipartite digraphs
• scientific article; zbMATH DE number 4061279
• Separation choosability and dense bipartite induced subgraphs
• Induced decompositions of highly dense graphs
• Bipartite induced density in triangle-free graphs
• On Finding Dense Subgraphs
• scientific article; zbMATH DE number 3943864
• On bipartite graphs with weak density of some subgraphs
• Finding dense subgraphs

Cites work

• A note on Thomassen's conjecture
• A survey of -boundedness
• Classes of graphs with low complexity: the case of classes with bounded linear rankwidth
• Dense graphs without 3-regular subgraphs
• Dense induced bipartite subgraphs in triangle-free graphs
• Every graph of sufficiently large average degree contains a C₄-free subgraph of large average degree
• Girth in graphs
• scientific article; zbMATH DE number 1696534 (Why is no real title available?)
• In absence of long chordless cycles, large tree-width becomes a local phenomenon
• Induced subdivisions and bounded expansion
• Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree
• On a conjecture of Thomassen concerning subgraphs of large girth
• On a problem of K. Zarankiewicz
• On finite set-systems whose every intersection is a kernel of a star
• Separation choosability and dense bipartite induced subgraphs

Cited in

(10)

• Problems and results in extremal combinatorics. I.
• \(C_4\)-free subgraphs with large average degree
• A result on large induced subgraphs with prescribed residues in bipartite graphs
• Detecting and Characterizing Small Dense Bipartite-Like Subgraphs by the Bipartiteness Ratio Measure
• On a conjecture of Thomassen concerning subgraphs of large girth
• Induced Turán problem in bipartite graphs
• Induced subdivisions in \(K_{s,s}\)-free graphs with polynomial average degree
• A survey of degree-boundedness
• Induced C₄-free subgraphs with large average degree
• Kővári-Sós-Turán theorem for hereditary families

This page was built for publication: Dense Induced Subgraphs of Dense Bipartite Graphs

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