Article in volume
Authors:
Title:
Biholes in balanced bipartite graphs
PDFSource:
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).
Close