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 条

[21] Induced Subgraph Isomorphism on proper interval and bipartite permutation graphs
Heggernes, Pinar
van 't Hof, Pim
Meister, Daniel
Villanger, Yngve
THEORETICAL COMPUTER SCIENCE, 2015, 562 : 252 - 269
[22] Induced subgraphs and tree decompositions VI. Graphs with 2-cutsets
Abrishami, Tara
Chudnovsky, Maria
Hajebi, Sepehr
Spirkl, Sophie
DISCRETE MATHEMATICS, 2025, 348 (01)
[23] Induced Subgraphs of Induced Subgraphs of Large Chromatic Number
Girao, Antonio
Illingworth, Freddie
Powierski, Emil
Savery, Michael
Scott, Alex
Tamitegama, Youri
Tan, Jane
COMBINATORICA, 2024, 44 (01) : 37 - 62
[24] Induced Subgraphs of Induced Subgraphs of Large Chromatic Number
António Girão
Freddie Illingworth
Emil Powierski
Michael Savery
Alex Scott
Youri Tamitegama
Jane Tan
Combinatorica, 2024, 44 : 37 - 62
[25] GROUPIES IN RANDOM BIPARTITE GRAPHS
Shang, Yilun
APPLICABLE ANALYSIS AND DISCRETE MATHEMATICS, 2010, 4 (02) : 278 - 283
[26] Superconnectivity of bipartite digraphs and graphs
Balbuena, C
Carmona, A
Fàbrega, J
Fiol, MA
DISCRETE MATHEMATICS, 1999, 197 (1-3) : 61 - 75
[27] On sensitivity in bipartite Cayley graphs
Garcia-Marco, Ignacio
Knauer, Kolja
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2022, 154 : 211 - 238
[28] Induced subgraphs of graphs with large chromatic number. IV. Consecutive holes
Scott, Alex
Seymour, Paul
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2018, 132 : 180 - 235
[29] Induced subgraphs of graphs with large chromatic number. I. Odd holes
Scott, Alex
Seymour, Paul
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2016, 121 : 68 - 84
[30] Sparse induced subgraphs of large treewidth
Bonnet, Edouard
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2025, 173 : 184 - 203

← 1 2 3 4 5 →