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

Question

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

Answer 1

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.

Answer 2

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