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 条
  • [31] On New Record Graphs Close to Bipartite Moore Graphs
    Gabriela Araujo
    Nacho López
    Graphs and Combinatorics, 2022, 38
  • [32] On New Record Graphs Close to Bipartite Moore Graphs
    Araujo, Gabriela
    Lopez, Nacho
    GRAPHS AND COMBINATORICS, 2022, 38 (04)
  • [33] Minimal induced subgraphs of two classes of 2-connected non-Hamiltonian graphs
    Cheriyan, Joseph
    Hajebi, Sepehr
    Qu, Zishen
    Spirkl, Sophie
    DISCRETE MATHEMATICS, 2022, 345 (07)
  • [34] On biregular bipartite graphs of small excess
    Filipovski, Slobodan
    Rivera, Alejandra Ramos
    Jajcay, Robert
    DISCRETE MATHEMATICS, 2019, 342 (07) : 2066 - 2076
  • [35] The size of bipartite graphs with a given girth
    Hoory, S
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2002, 86 (02) : 215 - 220
  • [36] Extremal bipartite graphs with high girth
    Balbuena, C.
    Garcia-Vazquez, P.
    Marcote, X.
    Valenzuela, J. C.
    ARS COMBINATORIA, 2007, 83 : 3 - 14
  • [37] Induced subgraphs of graphs with large chromatic number. VII. Gyarfas' complementation conjecture
    Scott, Alex
    Seymour, Paul
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2020, 142 : 43 - 55
  • [38] The Game of Cops and Robbers on Directed Graphs with Forbidden Subgraphs
    Ming-rui Liu
    Mei Lu
    Acta Mathematicae Applicatae Sinica, English Series, 2022, 38 : 684 - 689
  • [39] The Game of Cops and Robbers on Directed Graphs with Forbidden Subgraphs
    Liu, Ming-rui
    Lu, Mei
    ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES, 2022, 38 (03): : 684 - 689
  • [40] Light subgraphs in graphs with average degree at most four
    Wang, Tao
    DISCRETE MATHEMATICS, 2016, 339 (10) : 2581 - 2591
12345