Back to Search
Start Over
Optimal acyclic edge colouring of grid like graphs
- Source :
-
Discrete Mathematics . Nov2010, Vol. 310 Issue 21, p2769-2775. 7p. - Publication Year :
- 2010
-
Abstract
- Abstract: We determine the values of the acyclic chromatic index of a class of graphs referred to as -dimensional partial tori. These are graphs which can be expressed as the cartesian product of graphs each of which is an induced path or cycle. This class includes some known classes of graphs like -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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 0012365X
- Volume :
- 310
- Issue :
- 21
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 53311868
- Full Text :
- https://doi.org/10.1016/j.disc.2010.05.033