For any simple, finite, undirected graph $G=(V,E)$ and $v\in V$ let $N(v) = \{w\in V:\{v,w\}\in E\}$.

Suppose $G, H$ are finite, simple, undirected graphs and there is a bijection between the vertex sets $\varphi:V(G) \to V(H)$ such that for all $v,w\in V$ (not necessarily distinct) we have

$$|N(v)\cap N(w)| = |N(\varphi(v))\cap N(\varphi(w))|.$$

Does this imply that $\chi(G) = \chi(H)$?


No. And they can in fact be arbitrarily far apart. To see this let $G$ be two disjoint copies of $K_n$, and let $H$ be $K_{n,n}$ minus the edges of a perfect matching. Let $\varphi$ be a map that sends the two copies of $K_n$ in $G$ to the two sets in the bipartition of $H$.

Let $v$ and $w$ be vertices of $G$. Since both $G$ and $H$ are regular of degree $n-1$, we have $|N_G(v)|=|N_H(\varphi(v))|=n-1$. If $v$ and $w$ are in the same copy of $K_n$ in $G$, then $|N_G(v) \cap N_G(w)|=|N_H(\varphi(v)) \cap N_H(\varphi(w))|=n-2$. If $v$ and $w$ are in different copies of $K_n$ in $G$, then $|N_G(v) \cap N_G(w)|=|N_H(\varphi(v)) \cap N_H(\varphi(w))|=0$.

But $\chi(G)=n$, while $\chi(H)=2$.

  • 1
    $\begingroup$ Good example. Note that, in your example, you also get that the size of the common neighbourhood of a set of size k (for any k) is preserved by the bijection. $\endgroup$ – Jon Noel Mar 29 '16 at 15:20

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.