Skip to main content
deleted 2 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

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-1$$\chi(G)=n$, while $\chi(H)=2$.

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-1$, while $\chi(H)=2$.

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

Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

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-1$, while $\chi(H)=2$.