Join of two graphs bipartite?

Question

I have two bipartite graphs $(V,E)$ and $(V,E')$ (i. e. over the same set of vertices). Consider their join $(V,E\cup E')$. Are there any good criteria to check if the join is still bipartite?

Of course I could say something like »If there is no path of odd length using edges from $E$ or $E'$.« but maybe there is a more non-trivial reformulation of the problem?

Answer 1

There are some simple algorithms to check if a given graph is bipartite: Take a vertex $v$, let $T$ be a BFS spanning tree of $G$. Let $L_i$ be the set of vertices distance precisely $i$ from $v$ in $T$, for each nonnegative integer $i$ ($L_0$ is precisely $\{v\}$. Then every edge in $G \setminus T$ has (for some $i$), one endpoint in $L_i$ and the other either in $L_i$ or in $L_{i+1}$ because $T$ is a BFS tree, and of course every edge in $T$ has one endpoint in $L_i$ and the other in $L_{i+1}$ for some $i$. The graph $G$ is bipartite iff no edge in $G \setminus T$ has both endpoints in the same $L_i$, in which case the parts of $G$ are $\{v \in V(L_i)$ for some $i$ odd$\}$ and$\{v \in V(L_i)$ for some $i$ even$\}$.

This algorithm may not take into account that $G$ is the edge-disjoint union of two bipartite graphs but it still runs in linear time.

Answer 2

Wait, if both graphs are connected, then writing the parts of $G_1$ as $V_{11}$ and $V_{12}$ and the parts of $G_2$ as $V_{21}$ and $V_{22}$. Then the union is bipartite iff either $V_{11} = V_{21}$ and $V_{12} = V_{22}$ or $V_{11} = V_{22}$ and $V_{12} = V_{21}$.