KIT | KIT-Bibliothek | Impressum | Datenschutz

Induced Turán problem in bipartite graphs

Axenovich, Maria 1; Zimmermann, Jakob 1
1 Karlsruher Institut für Technologie (KIT)

Abstract:

The classical extremal function for a graph H, ex(Kn, H) is the largest number of edges in a subgraph of Kn that contains no subgraph isomorphic to H. Note that defining ex(Kn, H-ind) by forbidding induced subgraphs isomorphic to H is not very meaningful for a non-complete H since one can avoid it by considering a clique. For graphs F and H, let ex(Kn, {F, H-ind}) be the largest number of edges in an n-vertex graph that contains no subgraph isomorphic to F and no induced subgraph isomorphic to H. Determining this function asymptotically reduces to finding either ex(Kn, F) or ex(Kn, H), unless H is a biclique or both F and H are bipartite. Here, we consider the bipartite setting, ex(Kn,n, {F, H-ind}) when Kn is replaced with Kn,n, F is a biclique, and H is a bipartite graph. Our main result, a strengthening of a result by Sudakov and Tomon, implies that for any d >= 2 and any Kd,d-free bipartite graph H with each vertex in one part of degree either at most d or a full degree, so that there are at most d - 2 full degree vertices in that part, one has ex(Kn,n, {Kt,t, H-ind}) = o(n2-1/d). This provides an upper bound on the induced Tur & aacute;n number for a wide class of bipartite graphs and implies in particular an extremal result for bipartite graphs of bounded VC-dimension by Janzer and Pohoata.


Verlagsausgabe §
DOI: 10.5445/IR/1000175936
Veröffentlicht am 05.11.2024
Cover der Publikation
Zugehörige Institution(en) am KIT Fakultät für Mathematik (MATH)
Publikationstyp Zeitschriftenaufsatz
Publikationsdatum 15.01.2025
Sprache Englisch
Identifikator ISSN: 0166-218X
KITopen-ID: 1000175936
Erschienen in Discrete Applied Mathematics
Verlag Elsevier
Band 360
Seiten 497–505
Vorab online veröffentlicht am 22.10.2024
Nachgewiesen in Web of Science
Scopus
Dimensions
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page