Computer Science – Discrete Mathematics
Scientific paper
2012-01-12
Computer Science
Discrete Mathematics
5 pages, 3 figures
Scientific paper
Motivated by the problem in [6], which studies the relative efficiency of propositional proof systems, 2-edge colorings of complete bipartite graphs are investigated. It is shown that if the edges of $G=K_{n,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/\sqrt{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^2 \log n \sqrt{n \alpha(n^2,n) \log n})$ and giving a largest such fork forest is found.
Axenovich Maria
Krug Marcus
Osang Georg
Rutter Ignaz
No associations
LandOfFree
Fork-forests in bi-colored complete bipartite graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Fork-forests in bi-colored complete bipartite graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fork-forests in bi-colored complete bipartite graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-152151