This question is inspired by a recent related question.

Given a bipartition $V=B \cup C$ of the vertices of a graph, call an edge $B$-monochromatic (or $C$-monochromatic) if both ends are in $B$ (or in $C$) and monochromatic if either holds. Discuss the minimum number of monochromatic edges from a bipartition.

A graph is bipartite (by definition) if there is a bipartition with no monochromatic edges. An early theorem of graph theory is that this happens exactly when there are no odd cycles.

If there is a set of $k$ edge disjoint odd cycles then there must be at least $k$ monochromatic edges in any bipartition. Let $j$ be the total number of odd cycles. Also, let $\ell$ be the minimum size for a set of edges $F$ so that every odd cycle includes at least one edge from $F.$

The linked question is

Q1: If we insist on no B-monochromatic edges can we get a bipartition with no more than $j$ C-monochromatic edges?

With this formulation it might be more natural to ask

Q2: Can we get a bipartition with no more than $j$ monochromatic edges?

I suspect that $Q1$ (and hence $Q2$) may be true simply because either the structure with respect to odd cycles is quite simple or else there are a large number of odd cycles. So the right question might be something else, perhaps replacing $j$ with $\ell.$

Before continuing I'll note that this is related to the max-cut problem, minimizing the number of monochromatic edges is the same as maximizing the number of edges separating a vertex subset $B$ from its complement $C.$

In the graph below we can handle all the odd cycles by making the edges $bc$ and $b'c'$ $C$-monochromatic but then the same is true for edge $cc'.$

enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.