14
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ For question 2 what is the restriction on the partitions? $\endgroup$
    – Patrik
    Jun 1, 2015 at 12:51
  • $\begingroup$ @Patrik There are no restrictions on the partitions. $\endgroup$
    – hbm
    Nov 20, 2015 at 4:38

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$
1
  • $\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, 2015 at 13:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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