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?

  • 1
    $\begingroup$ For question 2 what is the restriction on the partitions? $\endgroup$ – Patrik Jun 1 '15 at 12:51
  • $\begingroup$ @Patrik There are no restrictions on the partitions. $\endgroup$ – 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$.

| cite | improve this answer | |
  • $\begingroup$ 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}$. $\endgroup$ – Patrik Jun 1 '15 at 13:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.