Cartesian Product and Acyclic Edge Colouring

Rahul Muthu, C. R. Subramanian

Published 2015-08-06Version 1

The acyclic chromatic index, denoted by $a'(G)$, of a graph $G$ is the minimum number of colours used in any proper edge colouring of $G$ such that the union of any two colour classes does not contain a cycle, that is, forms a forest. We show that $a'(G\Box H)\le a'(G) + a'(H)$ for any two graphs $G$ and $H$ such that $max\{a'(G), a'(H)\} > 1$. Here, $G \Box H$ denotes the cartesian product of $G$ and $H$. This extends a recent result of [15] where tight and constructive bounds on $a'(G)$ were obtained for a class of grid-like graphs which can be expressed as the cartesian product of a number of paths and cycles.