A result on large induced subgraphs with prescribed residues in bipartite graphs (Q2684886)

Summary: It was proved by \textit{A. D. Scott} [Graphs Comb. 17, No. 3, 539--553 (2001; Zbl 1010.05066)] that for every \(k\geqslant 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 \(\operatorname{deg}_H(v) \equiv 1\,\,(\mathrm{mod}\,\,k)\) for each \(v \in H\). Scott conjectured that \(c(k) = \Omega(1/k)\), which would be tight up to the multiplicative constant. We confirm this conjecture.