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)$?



Degrees and common neighbors
**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$.


