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?
Best Answer
At least you can get $K_{n,n}$. Let $G=(V,E)$ be a graph which $V=\{1,\ldots,n^{2}\}$ and $E=\{\{a,b\}; a\neq b , a \equiv b~(mod~n) ~or~ |a-b|<n\}$. Obviously, $\{kn+k+1; k=0,\ldots, n-1\}$ is an independent set of size $n$. Now consider $G^{c}$. So $\chi(G^{c})\geq n$. Consider these two colourings for $G^{c}$. Let $V_{i}=\{ a; a\equiv i~(mod~n) \}$ and $U_{i}=\{ (i-1)n+1,(i-1)n+2,\ldots,(i-1)n+n \}$, for $i=1,\ldots, n$.