# Bipartite graphs arising from two $k$-partitions of a given graph

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.

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

2. 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?

• For question 2 what is the restriction on the partitions? – Patrik Jun 1 '15 at 12:51
• @Patrik There are no restrictions on the partitions. – hbm Nov 20 '15 at 4:38

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$.
• Note that this can only work for $n>2$. Connected bipartite graphs only have one bipartition so $K_{2,2}$ can not be achieved. Another realization of $K_{n,n}$ with $n>2$ comes from the complement of $C_{2n}$. – Patrik Jun 1 '15 at 13:01