A note on large induced subgraphs with prescribed residues in bipartite graphs

Abstract: It was proved by Scott that for every

k g e 2

, there exists a constant

c (k) > 0

such that for every bipartite

n

-vertex graph

G

without isolated vertices, there exists an induced subgraph

H

of order at least

c (k) n

such that

e x t r m {d e g}_{H} (v) e q u i v 1 p m o d k

for each

v i n H

. Scott conjectured that

c (k) = O m e g a (1 / k)

, which would be tight up to the multiplicative constant. We confirm this conjecture.

This page was built for publication: A note on large induced subgraphs with prescribed residues in bipartite graphs