Geodesic
Biholes in balanced bipartite graphs
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 1203-1213 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

A bihole in a bipartite graph G with partite sets A and B is an independent set I in G with |I∩ A|=|I∩ 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 
@article{DMGT_2023_43_4_a17,
     author = {Ehard, Stefan and Mohr, Elena and Rautenbach, Dieter},
     title = {Biholes in balanced bipartite graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1203--1213},
     year = {2023},
     volume = {43},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a17/}
}
TY  - JOUR
AU  - Ehard, Stefan
AU  - Mohr, Elena
AU  - Rautenbach, Dieter
TI  - Biholes in balanced bipartite graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 1203
EP  - 1213
VL  - 43
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a17/
LA  - en
ID  - DMGT_2023_43_4_a17
ER  - 
%0 Journal Article
%A Ehard, Stefan
%A Mohr, Elena
%A Rautenbach, Dieter
%T Biholes in balanced bipartite graphs
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 1203-1213
%V 43
%N 4
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a17/
%G en
%F DMGT_2023_43_4_a17
Ehard, Stefan; Mohr, Elena; Rautenbach, Dieter. Biholes in balanced bipartite graphs. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 1203-1213. http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a17/

[1] 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

[2] 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

[3] Y. Caro, New results on the independence number (Technical Report, Tel-Aviv University, 1979).

[4] 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

[5] P. Turán, An extremal problem in graph theory, Matematikai és Fizikai Lapok 48 (1941) 436–452, in Hungarian.

[6] V.K. Wei, A Lower Bound on the Stability Number of a Simple Graph (Technical Memorandum, TM 81–11217–9, Bell Laboratories, 1981).