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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.