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 条

[41] Permanental bounds for the signless Laplacian matrix of bipartite graphs and unicyclic graphs
Li, Shuchao
Zhang, Li
LINEAR & MULTILINEAR ALGEBRA, 2011, 59 (02) : 145 - 158
[42] An algorithm for counting short cycles in bipartite graphs
Halford, TR
Chugg, KM
IEEE TRANSACTIONS ON INFORMATION THEORY, 2006, 52 (01) : 287 - 292
[43] Induced Subgraphs With Distinct Sizes
Alon, Noga
Kostochka, A. V.
RANDOM STRUCTURES & ALGORITHMS, 2009, 34 (01) : 45 - 53
[44] Induced subgraphs of prescribed size
Alon, N
Krivelevich, M
Sudakov, B
JOURNAL OF GRAPH THEORY, 2003, 43 (04) : 239 - 251
[45] On induced subgraphs of the Hamming graph
Dong, Dingding
JOURNAL OF GRAPH THEORY, 2021, 96 (01) : 160 - 166
[46] DISTINCT DEGREES IN INDUCED SUBGRAPHS
Jenssen, Matthew
Keevash, Peter
Long, Eoin
Yepremyan, Liana
PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 2020, 148 (09) : 3835 - 3846
[47] Minimal induced subgraphs of the class of 2-connected non-Hamiltonian wheel-free graphs
Chaniotis, Aristotelis
Qu, Zishen
Spirkl, Sophie
DISCRETE MATHEMATICS, 2023, 346 (03)
[48] CYCLES OF GIVEN SIZE IN A DENSE GRAPH
Harvey, Daniel J.
Wood, David R.
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2015, 29 (04) : 2336 - 2349
[49] A construction of small regular bipartite graphs of girth 8
Balbuena, Camino
DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2009, 11 (02) : 33 - 46
[50] Clique immersion in graphs without a fixed bipartite graph
Liu, Hong
Wang, Guanghui
Yang, Donglei
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2022, 157 : 346 - 365

← 1 2 3 4 5 →