On Edge-colorability of Products of Graphs


Bojan Mohar


Let $\chi'(G)$ denote the edge-chromatic number and $\Delta(G)$ the maximum vertex degree of a graph $G$. A graph $G$ is said to be {\it of class} 1 if $\chi'(G)=\Delta(G)$ and {\it of class} 2 otherwise. Some sufficient conditions for various graph products (the Cartesian, lexicographic, tensor and strong product) to be of class 1 are given.