Cartesian Product and Acyclic Edge Colouring

Abstract: 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 B o x H) l e a^{'} (G) + a^{'} (H)

for any two graphs

G

and

H

such that

m a x a^{'} (G), a^{'} (H) > 1

. Here,

G B o x 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.

This page was built for publication: Cartesian Product and Acyclic Edge Colouring