Let $G$ be an $n$-chromatic connected graph. Let $(V_1, V_2, \dots, V_n)$ and $(U_1, U_2, \dots, U_n)$ be two partitions of $V(G)$ corresponding to proper $n$-colorings of $G$.

Consider the bipartite graph $H = (X,Y,F)$ where $X=\{V_1, V_2, \dots, V_n\}$ and $Y= \{U_1, U_2, \dots, U_n\}$ and $\{V_i, U_j\} \in F$ if there is an edge between $V_i$ and $U_j$ in $G$.

It is easy to see that if the coloring are equivalent(the same up to permutations of colors), then H is isomorphic to $K_{n,n}- M$, $M$ is a perfect matching.

What kind of bipartite graphs do we get in the general case?

What happen when we consider partitions with $k$ parts where $k \le n$?

**EDIT**:
At least, can anything be said about the edge density of those bipartite graphs?