Sabidussi Theorem for chromatic number on cartesian product graph

Question

As usual, $\chi(G)$ denotes the chromatic number of a graph $G$.

Let $H$ and $G$ be two graphs with at least one vertex each.

Show that $ \chi (H \square G) = \max\{ \chi(H), \chi(G)\}$.

All the proofs i found were vague and didn't give me details.

Answer 1

Consider the adjacency matrix of the cartesian product of two graphs. It is equal to $\mathbf{A_1\otimes I_{n_2}}+\mathbf{I_{n_1}\otimes A_{n_2}}$ where $\mathbf{A_1},\mathbf{A_2}$ are adjacency matrices of individual graphs and $\otimes$ be the Kronecker product of matrices. Now, to give a coloring to the whole graph, it is necessary to give a number(color) to the diagonal entries of the adjacency matrix such that the same number is not given to two vertices which have adjacency ($a_{ii}\neq a_{jj}$ if $a_{ij}=1$). Consider the chromatic numbers of graphs having adjacency matrices $\mathbf{A_1}$ and $\mathbf{A_2}$. Let them be $\chi_1$ and $\chi_2$. Since the adjacency matrix of the product graph contains both the individual adjacency matrices as sub matrices each independent(as blocks in the full matrix- one set of blocks in the diagonal and the other set of blocks in non-diagonal entries), therefore, the entries on the diagonals of the two blocks would not interfere(is independent of the other). Thus, if we have colored the two diagonals of the two individual matrices independently using same set of colors, it also colors the whole adjacency matrix of the graph. Thus, chromatic number of the product graph is equal to maximum of $\chi_1,\chi_2$.

Answer 2

Let $N = max\{\chi (H),\chi (G)\}$

Suppose we have coloring functions $f_H: V(H) \rightarrow [0, ..., N-1]$ and $f_G: V(G) \rightarrow [0, ..., N-1]$ which assign different values to vertices that are adjacent in $H$ and $G$ respectively.

Then we can construct $f_{H \square G}: V(H \square G)\rightarrow [0, ..., N-1]$ as follows:

First, identify $V(H \square G)$ with $V(H) \times V(G)$ where $(h_1, g_1)$ is adjacent to $(h_2, g_2)$ if $h_1 = h_2$ and $g_1$ is adjacent to $g_2$ or vice versa. Then define $f_{H \square G}((h, g)) = f_H(h) + f_G(g) \mod N$.

Obviously this assigns $N$ colors to the points in $H \square G$. Suppose there were two adjacent points with identical colors.

Assume WLOG that $f_{H \square G}((h, g_1)) = f_{H \square G}((h, g_2))$ for some $g_1, g_2$ adjacent in $G$. (Otherwise, we can flip $H$ and $G$)

Applying the definition, we have

$f_H(h) + f_G(g_1) \mod N = f_H(h) + f_G(g_2) \mod N$

subtracting $f_H(h)$ gives

$f_G(g_1) \mod N = f_G(g_2) \mod N$

Since the range of $f_G$ is $[0, ..., N-1]$,

$f_G(g) \mod N = f_G(g)$ for all $g$.

This means we can remove the mod Ns.

$f_G(g_1) = f_G(g_2)$

Since $g_1, g_2$ are adjacent, this implies that $f_G$ is not a valid coloring of $G$, a contradiction.