Motivated by the problem in (Tveretina et al., 2009) [8], which studies problems from propositional proof complexity, 2-edge colorings of complete bipartite graphs are investigated. It is shown that if the edges of G=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 1, then there are at least n(1-1/2) vertex-disjoint forks with centers in the same partite set of G. 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(n ~2lognnα(~(n2),n)logn) and giving a largest such fork forest is found.
展开▼
机译：受（Tveretina et al。，2009）[8]中的问题的驱使，该问题从命题证明的复杂性研究问题，研究了完整二部图的2边着色。结果表明，如果G = Kn的边缘用黑色和白色着色，则黑色边缘的数量与白色边缘的数量最多相差1，则至少存在n（1-1 / 2 ）顶点不相交的叉子，其中心在G的同一部分集中。这里，叉子是由两个相邻的不同颜色的边缘形成的图形。边界很锐利。此外，找到了一种在时间O（n〜2lognnα（〜（n2），n）logn）上运行并给出最大的这种派生森林的算法。
展开▼
