Fork-forests in bi-colored complete bipartite graphs

Motivated by the problem in (Tveretina et al., 2009) [8], which studies problems from propositional proof complexity, 22-edge colorings of complete bipartite graphs are investigated. It is shown that if the edges of G=Kn,nG=Kn,n are colored with black and white such that the number of black edges differs from the number of white edges by at most 11, then there are at least n(1−1/2) vertex-disjoint forks with centers in the same partite set of GG. Here, a fork is a graph formed by two adjacent edges of different colors. The bound is sharp. Moreover, an algorithm running in time O(n2lognnα(n2,n)logn) and giving a largest such fork forest is found.