# Do graphs with identical degree matrix have the same chromatic number?

If $$G = (V, E)$$ is a simple, undirected graph and $$T \subseteq V$$, let $$N(T) = \{v \in V: \{v, t\}\in E \text{ for some }t\in T\}.$$

Given $$v\in V$$ we let $$N_0(v) = \{v\}$$ and $$N_{k+1}(v) = N_k(v) \cup N(N_k(v))$$ for all $$k\geq 1$$. The iterated degree sequence of $$v$$, denoted by $$(\text{deg}_k(v))_{k\in\omega}$$, is defined by $$\text{deg}_k(v) = |N_k(v)|\text{ for every }k\in \omega.$$

To every finite graph $$G = (V,E)$$ we associate the iterated degree matrix $$\mathbb{D}(G) \in \mathbb{N}^{n\times n}$$ (where $$n=|V|$$) in the following way: for every $$v\in V$$, take the first $$n$$ elements of its iterated degree sequence; order these $$n$$-element integer vectors lexicographically, and put these lexicographically ordered vectors in the matrix.

Question. Are there finite $$G_i = (V_i, E_i)$$ for $$i = 1,2$$ with $$|V_1| = |V_2|$$, $$\mathbb{D}(G_1) = \mathbb{D}(G_2)$$, but $$\chi(G_1) \neq \chi(G_2)$$?

There are such examples. Take two graphs with the same degrees but different chromatic number (for example, a cycle of length 6 and two triangles). Add a vertex of full degree to both.

Let $$V$$ be a finite group. Let $$A\subseteq V\setminus\{e\}$$ be a generating subset with $$A=A^{-1}$$. Then let $$E$$ be the collection of pairs $$\{u,v\}$$ where $$vu^{-1}\in A$$. Let $$\text{Cay}(V,A)=(V,E)$$. Then $$\text{Cay}(V,A)$$ is the simple undirected Cayley graph of the group $$V$$ with generating set $$A$$. The reason why we want to consider Cayley graphs is that in a Cayley graph, we have $$\text{deg}_k(u)=\text{deg}_k(v)$$ for every pair of vertices $$u,v$$, and this limits the possibilities for $$\mathbb{D}(G)$$. We also have a group theoretic characterization of the bipartitions of Cayley graphs.

Proposition: A mapping $$\phi:V\rightarrow\mathbb{Z}_2$$ is a bipartition of $$\text{Cay}(V,A)$$ with $$\phi(e)=0$$ if and only if $$\phi$$ is a group homomorphism with $$\phi[A]=1$$.

Proof: Let $$(V,E)=\text{Cay}(V,A)$$.

$$\leftarrow$$ If $$\{u,v\}\in E$$, then $$v=au$$ for some $$a\in A$$, but since $$\phi(a)=1$$, we know that $$\phi(v)=\phi(a)+\phi(u)=1+\phi(u)$$, so $$\phi(v)\neq\phi(u)$$. Therefore, $$(V,E)$$ is bipartite.

$$\rightarrow.$$ Since $$\phi(e)=0$$ and $$\{e,a\}\in E$$, we know that $$\phi(a)=1$$ for $$a\in A$$. By induction on $$r$$, we know that $$\phi(a_1\dots a_r)=[r]_2$$. Therefore, if $$u,v\in V$$, then $$u=a_1\dots a_r,v=b_1\dots b_s$$ for some $$a_1,\dots,a_r,b_1,\dots,b_s\in A$$. Therefore, $$\phi(uv)=\phi(a_1\dots a_rb_1\dots b_s)=[r+s]_2=[r]_2+[s]_2$$ $$=\phi(a_1\dots a_r)+\phi(b_1\dots b_s)=\phi(u)+\phi(v).$$ Therefore, $$\phi$$ is a group homomorphism. Q.E.D.

In particular, the bipartitions $$\phi:V\rightarrow\mathbb{Z}_2$$ are precisely the heap homomorphisms from $$V$$ to $$\mathbb{Z}_2$$.

The graph $$\text{Cay}(\mathbb{Z}_6,\{1,3,5\})$$ is bipartite while the graph $$\text{Cay}(S_3,\{(1,2),(2,3),(1,3)\})$$ is not. In each of these graphs and for each vertex $$u$$, we have $$\text{Deg}_1(u)=4,\text{Deg}_2(u)=6$$.