2015/08/06 by Rahul Muthu, Muthu, Rahul, C. R. Subramanian +1
Physics and Astronomy · #Color Science and Applications #Combinatorics (math.CO) #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.1508.01266
openalex publication_date 2015/08/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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)≤ 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.