Dense Induced Subgraphs of Dense Bipartite Graphs
Dense Induced Subgraphs of Dense Bipartite Graphs
复制标题
稠密二分图的稠密诱导子图
DOI：
--
复制
发表时间：
2020
影响因子：
0.8
通讯作者：
Rose McCarty
中科院分区：
文献类型：
--
作者：
Rose McCarty
证明了平均度足够大的二部图都有一个K_{t，t}-子图或一个平均度至少为t且围长至少为6的导出子图。我们猜想“$6$”可以用“$k$"代替，这加强了Kassen的一个猜想。为了支持这一猜想，我们证明了它适用于正则图。
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.