Total Colorings of Product Graphs

Abstract

A total coloring of a graph is an assignment of colors to all the elements of the graph in such a way that no two adjacent or incident elements receive the same color. In this paper, we prove Behzad–Vizing conjecture for product graphs. In particular, we obtain the tight bound for certain classes of graphs.

1 Introduction

All graphs in this paper are finite and simple. In a proper total coloring, any two elements that are either adjacent or incident are assigned different colors. The minimum number of colors needed for a proper total coloring is the total chromatic number of G, denoted by $\chi ''(G)$. Behzad [1, 2] and Vizing [13] conjectured [also called as Total Coloring Conjecture (TCC)] that for any graph G the following inequality holds:

$$\begin{aligned} \Delta (G)+1 \le \chi ''(G) \le \Delta (G)+2, \end{aligned}$$

where $\Delta (G)$ is the maximum degree of G. The lower bound is clearly the best possible. Graphs that need only $\Delta (G)+1$ colors are called graphs of type I. Graphs that need $\Delta (G)+2$ colors are called graphs of type II. For any graph G, it clear that from the Brooks’ theorem that the vertex chromatic number $\chi (G)\le \Delta (G)+1$ and by the Vizing’s theorem that the edge chromatic number $\chi '(G)\le \Delta (G)+1$. McDiarmid and S$\acute{\text {a}}$nchez-Arroyo [6] proved that determining the total chromatic number is NP-hard even for $\mu$-regular bipartite graphs, for each fixed $\mu \ge 3$.

Graph products were first defined by Sabidussi [8] and Vizing [12]. A lot of work was done on various topics related to graph products, but on the other hand there are still many questions open. The TCC was verified for graph products like cartesian product and direct product of certain classes of graphs. The TCC holds for cartesian product of graphs G and H, if the TCC holds for each of the graphs G and H. Seoud [9, 10] proved that the cartesian product graphs $P_m\Box P_n$, $m,n \ge 2$, except $P_2\Box P_2$ are of type I. Campos and de Mello [3] determined the total chromatic number of some bipartite graphs. The equitable total chromatic number of a graph G is the smallest integer $\mu$ for which G has a total $\mu$-coloring such that the numbers of elements of any two colors differs by at most one. Tong et al. [11] showed that the equitable total chromatic number of $C_m \Box C_n$ is $\Delta (C_m \Box C_n)+1$. Pranaver and Zmazek [7] proved that $\chi ''(P_m \times P_n)$ and $\chi ''(C_m \times P_n)$ are 5. Total coloring conjecture is still open for product graphs.

In this paper, we determine the total chromatic number for product graphs, in particular, direct product, strong product and lexicographic product for some classes of graphs. Also, we prove that the bound of TCC is tight for product graphs of some classes of graphs.

2 Product Graphs

In this paper, we consider the three of the four standard graph products. The four standard graph products are cartesian product, the direct product, the strong product and the lexicographic product. In [4], these products have been widely discussed with significant applications.

The cartesian product of G and H is a graph, denoted as $G \Box H$, whose vertex set is $V(G) \times V(H)$. Two vertices (g, h) and $(g',h')$ are adjacent precisely if $g=g'$ and $hh' \in E(H)$, or $gg' \in E(G)$ and $h=h'$. In other words, $V(G \Box H)=\{(g,h)| \ g\in V(G) \ \text {and} \ h\in V(H)\}$ and $E(G \Box H)=\{((g,h),(g',h'))| \ g=g', \ hh'\in E(H), \ \text {or} \ gg' \in E(G), \ h=h'\}$. The G- and H- layers are the induced subgraphs in $G \Box H$ on the vertex sets $G_u=\{(x,u)| \ x\in V(G)\}$ and $H_v=\{(v,x)| \ x \in V(H)\}$, respectively.

The direct product of G and H is a graph, denoted as $G \times H$, whose vertex set is $V(G) \times V(H)$ and for which vertices (g, h) and $(g',h')$ are adjacent precisely if $gg' \in E(G)$ and $hh' \in E(H)$. In other words, $V(G \times H)=\{(g,h)| \ g\in V(G) \ \text {and} \ h\in V(H)\}$ and $E(G \times H)= \{((g,h),(g',h'))| \ gg' \in E(G) \ \text {and} \ hh'\in E(H)\}$.

The strong product of G and H is a graph, denoted as $G\boxtimes H$ and defined by $V(G \boxtimes H)=\{(g,h)| \ g\in V(G) \ \text {and} \ h\in V(H)\}$ and $E(G\boxtimes H)=E(G\Box H)\cup E(G\times H)$.

The three products are commutative in the sense that $G*H\cong H*G$ for any two graphs G and H.

The lexicographic product of graphs G and H is the graph $G \circ H$ whose vertex set is $V (G) \times V (H)$, and for which $((g, h),(g',h'))$ is an edge of $G \circ H$ precisely if $(g,g') \in E(G)$, or $g = g'$ and $(h,h')\in E(H)$. The lexicographic product is also known as graph substitution, a name that bears witness to the fact that $G \circ H$ can be obtained from G by substituting a copy $H_g$ of H for every vertex g of G and then joining all vertices of $H_g$ with all vertices of $H_{g'}$ if $(g,g')\in E(G)$. The lexicographic product is associative but not commutative.

Since the total coloring of the cartesian product of almost all graphs were discussed [5, 15], in this paper we consider the remaining products.

2.1 Direct Product

A graph in which every vertex has the same degree is called a regular graph. A graph G is said to be irregular if at least two vertices have different degrees. A clique is a maximal complete subgraph of a graph. If v is a vertex of degree $\Delta (G)$ in G, then v is called a major vertex of G, otherwise a minor vertex of G. Suppose G has maximum degree $\Delta$. The core of G is the subgraph of G induced by the major vertices of G and denoted by $G_{\Delta }$.

Visualizing the direct product of graphs is not that much easy as cartesian product of graphs. Some care may be needed in interpreting the structure of the direct product of graphs. There is no much work done on total colorings of direct product of graphs.

We know that if G or H is bipartite then $G \times H$ is bipartite [4], and for bipartite graphs the Total Coloring Conjecture holds.

In the following theorem, we give the tight bound of TCC for the direct product of two complete graphs of odd degree.

Theorem 2.1

For any even positive integer n, $n\ge 4$, $\chi ''(K_n\times K_n)= \Delta (K_n\times K_n)+1$.

Fig. 1

K(n, n)

Proof

We denote a complete n partite graph by K(n, n) (see Fig. 1). In K(n, n), every vertex in one partition is adjacent to all the vertices in all other partitions. Let $(CQ)_j$ denotes a clique induced by the vertices $v_{ij}$ for each $i, i=0,1,\ldots ,n-1$ and $0\le j \le n-1$. We remove the edges of the clique $(CQ)_j$, $0\le j\le n-1$, from K(n, n). Hence, $K_n\times K_n$ is isomorphic to $K(n,n)-E(nK_n)$.

The complete n-partite graph K(n, n) is of type I for even $n\ge 4$ (Theorem 3.10 in [14], p. 22). Moreover, there is a total coloring of K(n, n) with $\chi ''(K(n,n))=\Delta (K(n,n))+1=n(n-1)+1$ colors such that the edges of the cliques $(CQ)_j$ are colored with the same set of $n-1$ colors (Lemma 3.8 in [14], p. 21). Removing these edges and the $n-1$ used colors results in a total coloring of $K_n\times K_n$ with $\chi ''(K(n,n))-\chi '(K_n)=n(n-1)+1-(n-1)=(n-1)^2+1=\Delta (K_n\times K_n)+1$ colors. $\square$

In the following theorem, we prove that $C_m\times C_n$ is of type I for some m and n. We give a total coloring of direct product of cycles by means of adjacency list. In a cycle, each vertex is adjacent to exactly two vertices. When we use the labelling $i\in [n]_0$, $[n]_0=\{0,1,2,\ldots ,n-1\}$, to the cycle $C_n$, every vertex i is adjacent to $i-1$ and $(i+1) \mod n$. The vertex $i=0$ is adjacent to the vertices 1 and $n-1$. Therefore, we use $n-1$ instead of -1 colors.

Theorem 2.2

For any positive integer n, $n\ge 3$, $\chi ''(C_m\times C_n)= \Delta (C_m \times C_n)+1$ if $m=3k,5l,8l, \ k=2,3,4,\ldots , \ l=1,2,\ldots$.

Proof

The edge colorings of $C_m \times C_n$ are given in the form of tables. A color in the table represents the color to all the edges $((i,j),(i',j'))$ for fixed i and for all $j\in [n]_0$, $i'$ and $j'$ are adjacent to i and j respectively.

Case 1 $m=3k$.

Subcase 1 k is odd.

The vertex coloring of $C_m\times C_n$ is given by $c(i,j)\,{=}\,{\left\{ \begin{array}{ll} 3 &{}\quad \text {if} \ i{=}3k, \ k{=}2,3,\ldots \\ 4 &{}\quad \text {if} \ i{=} 3 \\ i \mod 3 &{}\quad \text {otherwise}. \end{array}\right. }$

The edge coloring $c'((i,j),(i',j'))$ of $C_m \times C_n$ is as follows:

$(i,j)\backslash (i',j')$	$i'=i+1$		$i'=i-1$
	$j'=j+1$	$j'=j-1$	$j'=j+1$	$j'=j-1$
$(i=0,j)$	3	2	4	1
$(i=1,j)$	4	0	2	3
$(i=2,j)$	3	1	0	4
$(i=3,j)$	2	0	1	3
$(i\equiv 4 \mod 6,j)$	4	3	0	2
$(i\equiv 5 \mod 6,j)$	1	0	3	4
$(i\equiv 0 \mod 6,j)$	2	4	0	1
$(i\equiv 1 \mod 6,j)$	3	0	4	2
$(i\equiv 2 \mod 6,j)$	1	4	0	3
$(i\equiv 3 \mod 6,j)$	2	0	4	1

Subcase 2 k is even.

The vertex coloring of $C_m\times C_n$ is given by $c(i,j)= i \mod 3$.

The edge coloring $c'((i,j),(i',j'))$ of $C_m \times C_n$ is as follows:

$(i,j)\backslash (i',j')$	$i'=i+1$		$i'=i-1$
	$j'=j+1$	$j'=j-1$	$j'=j+1$	$j'=j-1$
$(i\equiv 0 \mod 6,j)$	2	3	1	4
$(i\equiv 1 \mod 6,j)$	0	4	3	2
$(i\equiv 2 \mod 6,j)$	3	1	4	0
$(i\equiv 3 \mod 6,j)$	2	4	1	3
$(i\equiv 4 \mod 6,j)$	0	3	4	2
$(i\equiv 5 \mod 6,j)$	4	1	3	0

Case 2 $m\equiv 0 \mod 5$.

The vertex coloring of $C_m\times C_n$ is given by $c(i,j)= i \mod 5$.

The edge coloring $c'((i,j),(i',j'))$ of $C_m \times C_n$ is as follows:

$(i,j)\backslash (i',j')$	$i'=i+1$		$i'=i-1$
	$j'=j+1$	$j'=j-1$	$j'=j+1$	$j'=j-1$
$(i\equiv 0 \mod 5,j)$	2	4	1	3
$(i\equiv 1 \mod 5,j)$	0	3	4	2
$(i\equiv 2 \mod 5,j)$	4	1	3	0
$(i\equiv 3 \mod 5,j)$	2	0	1	4
$(i\equiv 4 \mod 5,j)$	3	1	0	2

Case 3 $m\equiv 0 \mod 8$.

The vertex coloring of $C_m \times C_n$ is given by $c(i,j)\,{=}{\left\{ \begin{array}{ll} 0 &{} \text {if} \ i\equiv 0 \mod 8 \ \text {or} \ 5 \mod 8\\ 1 &{} \text {if} \ i\equiv 1 \mod 8 \ \text {or} \ 4 \mod 8 \\ 2 &{} \text {if} \ i\equiv 2 \mod 8 \ \text {or} \ 7 \mod 8\\ 4 &{} \text {if} \ i\equiv 3 \mod 8 \ \text {or} \ 6 \mod 8.\end{array}\right. }$

The edge coloring $c'((i,j),(i',j'))$ of $C_m \times C_n$ is as follows:

$(i,j)\backslash (i',j')$	$i'=i+1$		$i'=i-1$
	$j'=j+1$	$j'=j-1$	$j'=j+1$	$j'=j-1$
$(i\equiv 0 \mod 8,j)$	2	3	4	1
$(i\equiv 1 \mod 8,j)$	4	0	3	2
$(i\equiv 2 \mod 8,j)$	3	1	0	4
$(i\equiv 3 \mod 8,j)$	2	0	1	3
$(i\equiv 4 \mod 8,j)$	3	4	0	2
$(i\equiv 5 \mod 8,j)$	1	2	4	3
$(i\equiv 6 \mod 8,j)$	3	0	2	1
$(i\equiv 7 \mod 8,j)$	1	4	0	3

If both m and n are even, then $C_m$ and $C_n$ are bipartite graphs. Hence by Weichsels Theorem [4], which states that “Suppose G and H are connected nontrivial graphs. If at least one of G or H has an odd cycle, then $G\times H$ is connected. If both G and H are bipartite, then $G\times H$ has exactly two components”, $C_m\times C_n$ will be a disconnected graph with two components. Still the total chromatic number remains the same. $\square$

In our endower to prove $\chi ''(C_m \times C_n)=\Delta (C_m \times C_n)+1$ for any m and n, we prove this only for some classes of $C_m$. The above theorem may be true for the other classes. But it is easy to prove that $\chi ''(C_m \times C_n)\le \Delta (C_m \times C_n)+2$.

Remarks

• 1. We know that $C_{2n+1} \times C_{2n+1} \cong C_{2n+1} \Box C_{2n+1}$ [4] and we know that $\chi ''(C_{2n+1} \Box C_{2n+1})=5$. Hence $\chi ''(C_{2n+1} \times C_{2n+1})=5$.

• 2. Also, $C_4\times C_4\cong 2K_{4,4}$ and $\chi ''(K_{4,4})=6$. Therefore $\chi ''(C_4\times C_4)=6$.

2.2 Strong Product

As far as our literature survey is concerned, we believe that the total coloring for the strong product of graphs has not been studied. In [5], Kemnitz and Marangio proved that if $K_2 \Box H$ is a type I graph, then $G\Box H$ is also a type I graph, where G is a bipartite graph. This result can be extended to the strong product (see Theorem 2.3).

Theorem 2.3

If $K_2\boxtimes H$ is of type I, then $G\boxtimes H$ is of type I, where G is any bipartite graph.

Proof

Let $V(K_2)=\{0,1\}$. In $K_2\boxtimes H$, there will be two copies of H. Let us take the two copies of H as $H_0$-layer and $H_1$-layer. From our assumption, $\chi ''(K_2\boxtimes H)=\Delta (K_2\boxtimes H)+1=2\Delta (H)+2$. We partition the vertex set of G into two partitions X and Y. Color all elements of the layer $H_x$ for all $x\in X$ as $H_0$ and all elements of $H_y$ for all $y\in Y$ as $H_1$. Note that all vertices of $G\boxtimes H$ are properly colored.

Since G is bipartite, $\chi '(G)=\Delta (G)$. Moreover, in any edge coloring of G with $\Delta (G)$ colors each major vertex is incident with an edge of each color. Consider the set F of all edges of G of an arbitrary fixed color. For each edge $xy\in F$ color the edges between $H_x$ and $H_y$ in $G\boxtimes H$ as in $K_2\boxtimes H$.

So far, |F| copies of $K_2\boxtimes H$ and the remaining $|V(G)|-2|F|$ layers $H_v$ are colored in $G\boxtimes H$. The uncolored edges induce a bipartite graph of maximum degree $\Delta (G\boxtimes H)-\Delta (K_2 \boxtimes H)$ which implies that they can be colored with this number of additional colors.

Therefore, $\chi ''(G\boxtimes H)\le 2\Delta (H)+2+\Delta (G\boxtimes H)-\Delta (K_2\boxtimes H)=\Delta (G\boxtimes H)+1$, i.e., $G\boxtimes H$ is of type I. $\square$

Remark

Note that $K_2\boxtimes H$ is not always type I graph. For example $K_2\boxtimes K_3\cong K_6$ and $K_6$ is not a type I graph.

Corollary 2.1

For any positive integers m, n, $m\ge 2$ and $n\ge 3$, $\chi ''(P_m \boxtimes P_n)=\Delta (P_m \boxtimes P_n)+1$.

Proof

Let $\pi : V(P_2 \boxtimes P_n)\cup E(P_2 \boxtimes P_n)\rightarrow \mathcal {C}$ be a mapping, where $\mathcal {C}=\{0,1,2,\ldots ,4\}$.

First, let us consider $P_2\boxtimes P_n$. Here, $\Delta (P_2\boxtimes P_n)=5$. We give a total coloring as follows:

$$\begin{aligned}&\pi (i,j)=(i+2j+3) \mod 5, \ i=0,1,\\&\pi ((i,j),(i,j+1))=(2i+2j+1) \mod 5, \ i=0,1,\\&\begin{array}{l} \pi ((0,j+1),(1,j)) \\ \pi ((0,j),(1,j+1))\\ \end{array}\Bigg \} =(2(j+1)) \mod 5 ,\\&\pi ((0,j),(1,j))=5. \end{aligned}$$

From the above theorem, it is easy to see that $\chi ''(P_m \boxtimes P_n)=\Delta (P_m \boxtimes P_n)+1$, $m\ge 2$ and $n\ge 3$. $\square$

Remarks

• 1. Note that $P_1\boxtimes P_n$ is of type I if $n\ne 2$ and of type II if $n=2$. Also, $P_2\boxtimes P_2 \cong K_4$ is of type II.

• 2. We know that $K_m\boxtimes K_n\cong K_{mn}$, therefore $K_m\boxtimes K_n$ is of type I if both m and n are odd and of type II otherwise.

In the following theorem we give the upper bound of TCC for graphs $G \boxtimes H$, where G is a bipartite graph.

Theorem 2.4

For any bipartite graph G and any graph H with $\chi ''(K_2\boxtimes H)\le \Delta (K_2\boxtimes H)+2$ it holds that $\chi ''(G\boxtimes H)\le \Delta (G\boxtimes H)+2$.

Proof

Take the vertex set of $K_2$ as $V(K_2)=\{0,1\}$. There will be two copies of H, in $K_2\boxtimes H$. Denote these two copies of H as $H_0$-layer and $H_1$-layer. From our assumption, $\chi ''(K_2\boxtimes H)\le \Delta (K_2\boxtimes H)+2=2\Delta (H)+3$. Let X and Y be the two partitions of the vertex set of G. Color all elements of the layer $H_x$ for all $x\in X$ as $H_0$ and all elements of $H_y$ for all $y\in Y$ as $H_1$. In this coloring assignment all vertices of $G\boxtimes H$ are properly colored.

We know that for any bipartite graph G, $\chi '(G)=\Delta (G)$. All the $\Delta (G)$ colors are assigned to any major vertex v in G in the $\Delta (G)$-edge coloring. Consider the set F of all edges of G of an arbitrary fixed color. For each edge $xy\in F$ color the edges between $H_x$ and $H_y$ in $G\boxtimes H$ as in $K_2\boxtimes H$.

Here, we have colored the elements of |F| copies of $K_2\boxtimes H$ and the remaining $|V(G)|-2|F|$ layers $H_v$, in $G\boxtimes H$. The uncolored edges induce a bipartite graph of maximum degree $\Delta (G\boxtimes H)-\Delta (K_2 \boxtimes H)$ which implies that they can be colored with this number of additional colors.

Therefore, $\chi ''(G\boxtimes H)\le 2\Delta (H)+3+\Delta (G\boxtimes H)-\Delta (K_2\boxtimes H)=\Delta (G\boxtimes H)+2$. i.e, TCC holds for $G\boxtimes H$. $\square$

2.3 Lexicographic Product

As in the strong product, the lexicographic product of a bipartite graph with any arbitrary graph is not type I. In the following theorem, we prove the lexicographic product of a bipartite graph G and a graph H with $K_2\circ H$ satisfies TCC, is total colorable. We know that in general $G\circ H\ncong H \circ G$.

Theorem 2.5

For any bipartite graph G and any graph H with $\chi ''(K_2\circ H)\le \Delta (K_2 \circ H)+2$ it holds that $\chi ''(G\circ H) \le \Delta (G\circ H)+2$.

Proof

For any two graphs G and H, $\Delta (G\circ H)=n\Delta (G)+\Delta (H)$, where n is the order of the graph H. Let $V(K_2)=\{0,1\}$. In $K_2\circ H$, there will be two copies of H. Let us take the two copies of H as $H_0$-layer and $H_1$-layer. From our assumption, $\chi ''(K_2\circ H)\le \Delta (K_2\circ H)+2=n+\Delta (H)+2$. We partition the vertex set of G into two partitions X and Y. Color all elements of the layer $H_x$ for all $x\in X$ as $H_0$ and all elements of $H_y$ for all $y\in Y$ as $H_1$. Note that all vertices of $G\circ H$ are properly colored.

Since G is bipartite, the edges of G can be colored with $\Delta (G)$ colors. In this edge coloring all the major vertices are assigned all $\Delta (G)$ colors. Let F be the set of all edges of G of an arbitrary fixed color. Color the edges between $H_x$ and $H_y$ in $G\circ H$ as in $K_2\circ H$ for each edge $xy\in F$.

Here, |F| copies of $K_2 \circ H$ and remaining $|V(G)|-2|F|$ layers $H_v$ are colored in $G\circ H$ using at most $\Delta (K_2\circ H)+2$ colors. The uncolored edges induce a bipartite graph of maximum degree $\Delta (G\circ H)-\Delta (K_2\circ H)=n(\Delta (G)-1)$ which implies that they can be colored with this number of additional colors.

Therefore, $\chi ''(G\circ H)\le \Delta (K_2\circ H)+2+\Delta (G\circ H)-\Delta (K_2\circ H)=\Delta (G\circ H)+2$. i.e, TCC holds for $G\circ H$. $\square$

In the following theorems we prove the tight bound of TCC.

Lemma 2.1

$\chi ''(P_2 \circ P_3)=6$.

Proof

The total coloring of $P_2 \circ P_3$ is shown in Fig. 2. In this case, $\Delta (P_2 \circ P_3)=5$. $\square$

Fig. 2

Total coloring of $P_2 \circ P_3$

Theorem 2.6

Let G be a bipartite graph. Then, $\chi ''(G \circ P_3)= \Delta (G \circ P_3)+1$.

Proof

Let X and Y be the two vertex partition sets of G and set $H\cong P_3$. Color all elements of the layer $H_x$ for all $x\in X$ as the first $P_3$-layer and all elements of $H_y$ for all $y\in Y$ as the second $P_3$-layer in the coloring of Lemma 2.1. Consider the set F of all edges of G of an arbitrary fixed color in an edge coloring with $\Delta (G)$ colors. For each edge $xy\in F$ color the edges between $H_x$ and $H_y$ in $G\circ P_3$ as in Lemma 2.1.

Since G is bipartite, the uncolored edges induce a bipartite graph of maximum degree $\Delta (G\circ P_3)-5$, which implies that they can be colored with this number of additional colors.

Therefore, $\chi ''(G\circ P_3)\le 6+\Delta (G\circ P_3)-5=\Delta (G\circ P_3)+1$. i.e, $G\circ P_3$ is of type I. $\square$

Corollary 2.2

For any positive integer n, $n\ge 3$, $\chi ''(P_n\circ P_3)=9$.

Proof

The graph $P_n \circ P_3$, $n>2$, is a n layered $P_3$ graph. In this case, $\Delta (P_n\circ P_3)=8$. If n is even, then $P_n \circ P_3$ contains $\frac{n}{2}$ copies of $P_2 \circ P_3$ as an induced subgraph. Now, we color these $\frac{n}{2}$ copies of $P_2\circ P_3$ using 6 colors as shown in Lemma 2.1. Now, the edges between each copies of $P_2 \circ P_3$ are colored with three new colors. If n is odd, then $P_n \circ P_3$ is $\frac{n-1}{2}$ copies of $P_2\circ P_3$ and a $P_3$- layer. These $\frac{n-1}{2}$ copies of $P_2\circ P_3$ can be colored as in the above case and the elements in $P_3$ of the nth-layer can colored as the elements of $P_3$ in the first layer. Also, the edges between each of the copies of $P_2 \circ P_3$ and the edges between the $(n-1)$th-layer and the nth-layer can be colored with three new colors. Hence, in both the cases, we used only 9 colors for the total coloring of $P_n \circ P_3$. $\square$