I've been battling with this question for a few days now: We have 5 graphs (G1, G2, G3, G4, G5), each of which is a bipartite graph. V is divided into Ai, Bi (for each graph respectively). Let G be the merged graph (merging all edges and removing duplicates). What would be the maximal number of colors required to color it?
Each and every attempt I make at resolving this ends up being related to the size of V when the intuition dictates otherwise.
The more edges in each graph the closer G becomes to being K (a full graph).
Does the largest rank define the coloring? What am I missing here?
Well certainly 32 colors is enough, just remember the colors in each individual graph. Moreover it's not too hard to construct five graphs which require 32 total colors: Each one is a copy of $K_{16,16}$ where we label the vertices from 0 to 31 and the parts of $G_n$ are determined by the $n$th binary digit. Of course smaller graphs might need fewer colors.