On the $\delta$-chromatic numbers of the Cartesian products of graphs

$(\Longrightarrow)$ Let $u=(u_{1},u_{2})$ and $v=(v_{1},v_{2})$ be distinct vertices in $(G\square H)_{\delta}$ where $uv\in E((G\square H)_{\delta})$. It follows that either

• •

  $uv\in E(G\square H)$ and $d_{G\square H}(u)\neq d_{G\square H}(v)$, or

• •

  $uv\not\in E(G\square H)$ and $d_{G\square H}(u)=d_{G\square H}(v)$.

In case $uv\in E(G\square H)$ and $d_{G\square H}(u)\neq d_{G\square H}(v)$, without loss of generality, we suppose that $u_{1}=v_{1}$, $u_{2}\neq v_{2}$ and $u_{2}v_{2}\in E(H)$. Since $d_{G}(u_{1})=d_{G}(v_{1})$, it follows that $d_{H}(u_{2})\neq d_{H}(v_{2})$. Thus $u_{2}v_{2}\in E(H_{\delta})$. Hence $uv\in E(G_{\delta}\square H_{\delta})$. In case $uv\not\in E(G\square H)$ and $d_{G\square H}(u)=d_{G\square H}(v)$, we have $u_{1}\neq v_{1}$ and $u_{2}\neq v_{2}$. Thus $uv\in S$.

$(\Longleftarrow)$ Let $uv\in E(G_{\delta}\square H_{\delta})\cup S$. Consider $uv\in E(G_{\delta}\square H_{\delta})$. Without loss of generality, we suppose that $u_{1}=v_{1}$, $u_{2}\neq v_{2}$ and $u_{2}v_{2}\in E(H_{\delta})$. If $d_{G\square H}(u)=d_{G\square H}(v)$, then $d_{H}(u_{2})=d_{H}(v_{2})$. Thus $u_{2}v_{2}\not\in E(H)$. Hence $uv\not\in E(G\square H)$. Since $d_{G\square H}(u)=d_{G\square H}(v)$, we have $uv\in E((G\square H)_{\delta})$. If $d_{G\square H}(u)\neq d_{G\square H}(v)$, then $d_{H}(u_{2})\neq d_{H}(v_{2})$. Thus $u_{2}v_{2}\in E(H)$ and $uv\in E(G\square H)$. Since $d_{G\square H}(u)\neq d_{G\square H}(v)$, we have $uv\in E((G\square H)_{\delta})$. Now, we consider $uv\in S$. We have that $u_{1}\neq v_{1}$ and $u_{2}\neq v_{2}$. So $uv\notin E(G\square H)$. Since $d_{G\square H}(u)=d_{G\square H}(v)$, it follows that $uv\in E((G\square H)_{\delta})$. ∎

It is well-known that two vertices $u=(u_{1},\dots,u_{k})$ and $(v_{1},\dots,v_{k})$ in $G_{1}\square\dots\square G_{k}$ are adjacent if and only if there is exactly one $i$ such that $u_{i}\neq v_{i}$ and $u_{i}v_{i}\in E(G_{i})$. The rest of the proof follows similar arguments as in Theorem 5. ∎

From Theorem 7, we need to show that $S=\emptyset$ if and only if there are at most one $i$ such that $G_{i}\neq K_{1}$.

Suppose that there are $i\neq j$ such that $G_{i}\neq K_{1}$ and $G_{j}\neq K_{1}$. Choose $u=(u_{1},\dots,u_{k})$ and $v=(v_{1},\dots,v_{2})$ such that $u_{i}\neq v_{i}$, $u_{j}\neq v_{j}$, $d_{G_{i}}(u_{i})=d_{G_{i}}(v_{i})$, $d_{G_{j}}(u_{j})=d_{G_{j}}(v_{j})$ and $u_{\ell}=v_{\ell}$ for all $\ell\not\in\{i,j\}$. So $d_{G_{1}\square\cdots\square G_{k}}(u)=d_{G_{1}\square\cdots\square G_{k}}(v)$. Then $uv\in S$. Hence $S\neq\emptyset$.

The converse is obvious. ∎

The proof follows directly from Theorem 3 and 7. ∎

By Theorem 5 and the assumption that any positive degree difference of vertices in $G$ is not equal to that of in $H$, the edges in $S$ are $uv$ where $u=(u_{1},u_{2})$, $v=(v_{1},v_{2})$ such that $u_{1}\neq v_{1}$, $u_{2}\neq v_{2}$, $d_{G}(u_{1})=d_{G}(v_{1})$ and $d_{H}(u_{2})=d_{H}(v_{2})$. We partition $V(H)$ according to vertex degree into $W_{1},W_{2},\dots,W_{m(H)}$. Write $W_{j}=\{h_{j,1},h_{j,2},\dots,h_{j,n_{j}}\}$ for $1\leq j\leq m(H)$.

Define $p=\max(\chi_{\delta}(G),m(H))$. Let $c_{0}:V(G)\to\{1,2,\dots,\chi_{\delta}(G)\}$ be a proper coloring of $G_{\delta}$. We define a coloring $c:V(G)\times V(H)\to\{1,2,\dots,n_{\max}(H)\cdot p\}$ as

for $k=1,\dots,n_{j}$, where $f(g,j)\in\{1,2,\dots,p\}$ and $f(g,j)\equiv c_{0}(g)+j-1\pmod{p}$. The first copy of $G$ in $W_{1}$ gets the original coloring $c_{0}$, while we keep adding $p$ to the coloring of each other copy of $G$ in $W_{1}$. In other $W_{j}$, we perform different cyclic permutations modulo $p$ to $c_{0}$ and assign it to the first copy of $G$ in $W_{j}$. See Table 1 for an example. We see that the vertices in the same copy of $G$ received a coloring equivalent to $c_{0}$ and a cyclic permutation modulo $p$ up to an additive constant $(k-1)p$ for some $k=1,\dots,n_{j}$. For a fixed $g\in V(G)$, the vertices in the same copy of $H$, written in the form $(g,h_{j,k})$ where $1\leq j\leq m(H)$ and $1\leq k\leq n_{j}$, received distinct colors because $j\leq p$ and $k\leq n_{\max}(H)$.

Lastly, any endpoints of an edge in $S$ are of the form $(g,h_{j,k})$ and $(g^{\prime},h_{j,k^{\prime}})$ where $g\neq g^{\prime}$ and $k\neq k^{\prime}$, which received different colors as $k\neq k^{\prime}$. The sharpness of the bound appears in Theorem 13. ∎

Let $P_{3}=v_{1}v_{2}v_{3}$. It is easy to see that $\chi_{\delta}(C_{n})=\chi(\overline{C_{n}})=\left\lceil\frac{n}{2}\right\rceil$. Since $C_{n}$ is regular, it also follows that $d_{C_{n}\square P_{3}}(u,v_{1})=d_{C_{n}\square P_{3}}(w,v_{3})$ for all $u,w\in V(C_{n})$. Since $(u,v_{1})$ is not adjacent to $(w,v_{3})$ in $C_{n}\square P_{3}$, it follows that each vertex in the first copy of $C_{n}$ is adjacent to all the vertices in the third copy of $C_{n}$ in $(C_{n}\square P_{3})_{\delta}$. Hence the colors used in the two copies do not coincide. Thus $\chi_{\delta}(C_{n}\square P_{3})\geq 2\chi_{\delta}(C_{n})$. By Corollary 12, we can conclude that $\chi_{\delta}(C_{n}\square P_{3})=2\chi_{\delta}(C_{n})$. ∎

Let $G=S_{1,m}$ and $H=P_{3}$. Theorem 11 gives the desired upper bound. ∎

Let $r\in V(H)$. Note that $d_{G}(u)=|V(H)|$. Since $d_{G\square P_{3}}(r,v_{i})=d_{G}(r)+d_{P_{3}}(v_{i})\leq k+3<d_{G}(u)+1\leq d_{G\square P_{3}}(u,v_{j})$ for $i,j\in\{1,2,3\}$, we have $(r,v_{i})$ and $(u,v_{j})$ are adjacent in $(G\square P_{3})_{\delta}$ if and only if $i=j$.

Let $H_{\delta}^{i}$ be the $i$-th copy of $H_{\delta}$ in $G_{\delta}$ for $i=1,2,3$. Next, we construct a proper coloring $c$ as follows. We trivially color $H_{\delta}^{1}$, as a copy of $H_{\delta}$, by a $\chi_{\delta}(H)$-coloring. Since each vertex in $H_{\delta}^{1}$ is adjacent to any vertices in $H_{\delta}^{3}$, it requires $2\chi_{\delta}(H)$ colors for $H^{1}_{\delta}$ and $H^{3}_{\delta}$. We color $H^{3}_{\delta}$ using $c(r,v_{3})=c(r,v_{1})+\chi_{\delta}(H)$. For $i=1,3$, we notice that a vertex $(r,v_{i})\in V(H^{i}_{\delta})$ and $(s,v_{2})\in V(H^{2}_{\delta})$ are adjacent if and only if $r=s$. We let $c(r,v_{2})=c(r,v_{1})+1$ if $1\leq c(r,v_{1})\leq\chi_{\delta}(H)-1$; otherwise, $c(r,v_{2})=1$. Lastly, we color $(u,v_{1})$, $(u,v_{2})$ and $(u,v_{3})$ by $\chi_{\delta}(H)+1$, $\chi_{\delta}(H)+2$ and $1$, respectively. This gives a proper coloring of $(G\square P_{3})_{\delta}$ with $2\chi_{\delta}(H)$ colors. ∎

Let $V(S_{1,n})=\{0,1,\dots,k\}$ where $d_{S_{1,k}}(0)=k$ for $k=n,m$. An $mn$-coloring on $(S_{1,m}\square S_{1,n})_{\delta}$ is

as shown in Fig. 1. In addition, the set $\{(i,j):1\leq i\leq m,1\leq j\leq n\}$ forms an $mn$-clique in $(S_{1,m}\square S_{1,n})_{\delta}$. ∎

Let $V(S_{1,m})=\{0,1,\dots,m\}$ where $d_{S_{1,m}}(0)=m$ and Let $V(P_{n})=\{1,2,\dots,n\}$ where $d_{P_{n}}(1)=d_{P_{n}}(n)=1$.

When $n=3$, Theorem 15 gives $\chi_{\delta}(S_{1,m}\square P_{3})\leq 2m$. Since the set $\{(i,j)\in V((S_{1,m}\square P_{3})_{\delta}):1\leq i\leq m,j=1,3\}$ forms a $2m$-clique in $(S_{1,m}\square P_{3})_{\delta}$, we get $\chi_{\delta}(S_{1,m}\square P_{3})=2m$.

When $n=4$, Theorem 11 with $G=P_{4}$ and $H=S_{1,m}$ gives $\chi_{\delta}(S_{1,m}\square P_{4})=\chi_{\delta}(P_{4}\square S_{1,m})\leq 2m$. The set $\{(i,j)\in V((S_{1,m}\square P_{4})_{\delta}):1\leq i\leq m,j=1,4\}$ forms a $2m$-clique in $(S_{1,m}\square P_{4})_{\delta}$. Hence $\chi_{\delta}(S_{1,m}\square P_{4})=2m$.

When $n\geq 5$, we let $k=\lceil\frac{n-2}{2}\rceil$. A coloring is

as shown in Fig. 2. We thus have a proper $km$-coloring of $(S_{1,m}\square P_{n})_{\delta}$. In addition, the set $\{(i,j)\in V((S_{1,m}\square P_{n})_{\delta}):1\leq i\leq m\text{ and }2\leq j\leq n-1\text{ and }j\text{ is even}\}$ forms a clique of size $m\left\lceil\frac{n-2}{2}\right\rceil$ in $(S_{1,m}\square P_{n})_{\delta}$. ∎

Suppose $2\left\lceil\frac{n-2}{2}\right\rceil+2\left\lceil\frac{k-2}{2}\right\rceil+1\geq\left\lceil\frac{(n-2)(k-2)}{2}\right\rceil$.

We have

Thus $n\leq\frac{4k-10}{k-4}<6$ when $k\geq 8$, which is a contradiction.

We have

Thus $n\leq\frac{3k-6}{k-4}\leq\frac{9}{2}$, which is not possible when $k\geq 8$. The same argument can be applied when $n$ is even and $k$ is odd.

Thus $n\leq\frac{3k-5}{k-3}\leq\frac{19}{5}$, which is not possible when $k\geq 8$.

Therefore $2\left\lceil\frac{n-2}{2}\right\rceil+2\left\lceil\frac{k-2}{2}\right\rceil+1<\left\lceil\frac{(n-2)(k-2)}{2}\right\rceil.$ ∎