2
$\begingroup$

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

$\endgroup$

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.