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 条
  • [11] Odd Induced Subgraphs in Planar Graphs with Large Girth
    Rao, Mengjiao
    Hou, Jianfeng
    Zeng, Qinghou
    GRAPHS AND COMBINATORICS, 2022, 38 (04)
  • [12] Dense graphs have K3,t minors
    Kostochka, A. V.
    Prince, N.
    DISCRETE MATHEMATICS, 2010, 310 (20) : 2637 - 2654
  • [13] On the number of connected subgraphs of graphs
    Dinesh Pandey
    Kamal Lochan Patra
    Indian Journal of Pure and Applied Mathematics, 2021, 52 : 571 - 583
  • [14] On the number of connected subgraphs of graphs
    Pandey, Dinesh
    Patra, Kamal Lochan
    INDIAN JOURNAL OF PURE & APPLIED MATHEMATICS, 2021, 52 (02) : 571 - 583
  • [15] Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs
    Martin, Barnaby
    Paulusma, Daniel
    Smith, Siani
    van Leeuwen, Erik Jan
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE (WG 2022), 2022, 13453 : 398 - 411
  • [16] Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs
    Martin, Barnaby
    Paulusma, Daniel
    Smith, Siani
    van Leeuwen, Erik Jan
    ALGORITHMICA, 2023, 85 (09) : 2580 - 2604
  • [17] Characterizing subgraphs of Hamming graphs
    Klavzar, S
    Peterin, I
    JOURNAL OF GRAPH THEORY, 2005, 49 (04) : 302 - 312
  • [18] Graphs having small number of sizes on induced k-subgraphs
    Axenovich, Maria
    Balogh, Jozsef
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2007, 21 (01) : 264 - 272
  • [19] Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs
    Barnaby Martin
    Daniël Paulusma
    Siani Smith
    Erik Jan van Leeuwen
    Algorithmica, 2023, 85 : 2580 - 2604
  • [20] NORDHAUS-GADDUM INEQUALITIES FOR THE NUMBER OF CONNECTED INDUCED SUBGRAPHS IN GRAPHS
    Andriantiana, Eric O. D.
    Dossou-Olory, Audace A. V.
    QUAESTIONES MATHEMATICAE, 2022, 45 (08) : 1191 - 1213
12345