Degrees and common neighbors

Question

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

Answer 1

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