DMGT

Article in volume

Authors:

S. Ehard

Stefan Ehard

Ulm University

email: ehard.stefan@gmx.de

E. Mohr

Elena Mohr

Ulm University

email: elena.mohr@uni-ulm.de

D. Rautenbach

Dieter Rautenbach

University of Ulm

email: dieter.rautenbach@uni-ulm.de

Title:

Biholes in balanced bipartite graphs

PDF

Source:

Discussiones Mathematicae Graph Theory 43(4) (2023) 1203-1213

Received: 2021-03-31 , Revised: 2021-07-07 , Accepted: 2021-07-07 , Available online: 2021-07-20 , https://doi.org/10.7151/dmgt.2423

Abstract:

A bihole in a bipartite graph

$G$ with partite sets

$A$ and

$B$ is an independent set

$I$ in

$G$ with

$|I\cap A|=|I\cap B|$ . We prove lower bounds on the largest order of biholes in balanced bipartite graphs subject to conditions involving the vertex degrees and the average degree.

Keywords:

bihole, independent set

References:

M. Axenovich, C. Tompkins and L. Weber, Large homogeneous subgraphs in bipartite graphs with forbidden induced subgraphs, J. Graph Theory 97 (2021) 34–46.
https://doi.org/10.1002/jgt.22639
M. Axenovich, J.-S. Sereni, R. Snyder and L. Weber, Bipartite independence number in graphs with bounded maximum degree, SIAM J. Discrete Math. 35 (2021) 1136–1148.
https://doi.org/10.1137/20M1321760
Y. Caro, New results on the independence number (Technical Report, Tel-Aviv University, 1979).
M. Molloy and B. Reed, Graph Colouring and the Probabilistic Method (Springer-Verlag, Berlin, 2002).
https://doi.org/10.1007/978-3-642-04016-0
P. Turán, An extremal problem in graph theory, Matematikai és Fizikai Lapok 48 (1941) 436–452, in Hungarian.
V.K. Wei, A Lower Bound on the Stability Number of a Simple Graph (Technical Memorandum, TM 81–11217–9, Bell Laboratories, 1981).