In this paper we investigate the bipartite analogue of the strong Erdős-Hajnal property. We prove that for every forest H and every τ with 0<τ≤1, there exists ε>0, such that if G has a bipartition (A,B) and does not contain H as an induced subgraph, and has at most (1−τ)|A|⋅|B| edges, then there is a stable set X of G with |X∩A|≥ε|A| and |X∩B|≥ε|B|. No graphs H except forests have this property.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Bipartite graph
- Induced subgraph
- Pure pair