Header menu link for other important links
X
Optimal acyclic edge colouring of grid like graphs
Rahul Muthu, , Subramanian C.R.
Published in Elsevier B.V.
2010
Volume: 310
   
Issue: 21
Pages: 2769 - 2775
Abstract
We determine the values of the acyclic chromatic index of a class of graphs referred to as d-dimensional partial tori. These are graphs which can be expressed as the cartesian product of d graphs each of which is an induced path or cycle. This class includes some known classes of graphs like d-dimensional meshes, hypercubes, tori, etc. Our estimates are exact except when the graph is a product of a path and a number of odd cycles, in which case the estimates differ by an additive factor of at most 1. Our results are also constructive and provide an optimal (or almost optimal) acyclic edge colouring in polynomial time. © 2010 Elsevier B.V. All rights reserved.
About the journal
JournalData powered by TypesetDiscrete Mathematics
PublisherData powered by TypesetElsevier B.V.
ISSN0012365X
Open AccessNo