DENSE INDUCED SUBGRAPHS OF DENSE BIPARTITE GRAPHS

被引：6
|
作者：
McCarty, Rose [1 ]
机构：
[1] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON, Canada
来源：
SIAM JOURNAL ON DISCRETE MATHEMATICS | 2021年 / 35卷 / 02期
关键词：
average-degree; girth; induced subgraphs; INDUCED SUBDIVISIONS;
D O I：
10.1137/20M1370744
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We prove that every bipartite graph of sufficiently large average degree has either a Kt,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 any constant "k," which strengthens a conjecture of Thomassen. In support of this conjecture, we show that it holds for regular graphs.
引用
收藏
页码：661 / 667
页数：7
相关论文
共 50 条
  • [1] Small minors in dense graphs
    Fiorini, Samuel
    Joret, Gwenael
    Theis, Dirk Oliver
    Wood, David R.
    EUROPEAN JOURNAL OF COMBINATORICS, 2012, 33 (06) : 1226 - 1245
  • [2] Maximising the number of connected induced subgraphs of unicyclic graphs
    Dossou-Olory, Audace A. V.
    TURKISH JOURNAL OF MATHEMATICS, 2022, 46 (08) : 3359 - 3372
  • [3] Coloring graphs with forbidden induced subgraphs
    Chudnovsky, Maria
    PROCEEDINGS OF THE INTERNATIONAL CONGRESS OF MATHEMATICIANS (ICM 2014), VOL IV, 2014, : 291 - 302
  • [4] Forbidden Induced Bipartite Graphs
    Allen, Peter
    JOURNAL OF GRAPH THEORY, 2009, 60 (03) : 219 - 241
  • [5] Characterizing Flag Graphs and Induced Subgraphs of Cartesian Product Graphs
    Iztok Peterin
    Order, 2004, 21 : 283 - 292
  • [6] Characterizing flag graphs and induced subgraphs of cartesian product graphs
    Peterin, I
    ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2004, 21 (04): : 283 - 292
  • [7] On the recognition of de Bruijn graphs and their induced subgraphs
    Blazewicz, J
    Formanowicz, P
    Kasprzak, M
    Kobler, D
    DISCRETE MATHEMATICS, 2002, 245 (1-3) : 81 - 92
  • [8] Hitting forbidden induced subgraphs on bounded treewidth graphs
    Sau, Ignasi
    Souza, Ueverton dos Santos
    INFORMATION AND COMPUTATION, 2021, 281
  • [9] FORBIDDEN INDUCED SUBGRAPHS OF DOUBLE-SPLIT GRAPHS
    Alexeev, Boris
    Fradkin, Alexandra
    Kim, Ilhee
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2012, 26 (01) : 1 - 14
  • [10] Odd Induced Subgraphs in Planar Graphs with Large Girth
    Mengjiao Rao
    Jianfeng Hou
    Qinghou Zeng
    Graphs and Combinatorics, 2022, 38
12345