Cartesian Product and Acyclic Edge Colouring

Abstract

The acyclic chromatic index, denoted by $a^{\prime }(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^{\prime }(G\square H)\le a^{\prime }(G)+a^{\prime }(H)$ for any two graphs $G$ and $H$ such that $max\{a^{\prime }(G),a^{\prime }(H)\}>1$. Here, $G\square H$ denotes the cartesian product of $G$ and $H$. This extends a recent result of [15] where tight and constructive bounds on $a^{\prime }(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.

Cited by in corpus (1)

• Improved Upper Bounds on $a^{\prime }(G\square H)$