Acyclic edge colouring of subgraphs of hypercubes

Abstract

Acyclic edge colouring is a very important combinatorial optimization problem, which many researchers are currently working on. Acyclic edge colouring is assignment of colours to vertices or edges of the graph such that, no two colour induced subgraph contains any cycle. In its most general form, it is a very difficult problem and thus research work on this problem, usually focuses on some limited aspect. In particular one approach to this problem is to find exact values for the acyclic chromatic index for special families of graphs. One might also look for corresponding efficient algorithms, for such optimal colourings. However, it is essential to study a few papers on this problem of acyclic edge colouring in order to develop one’s techniques and solve a new aspect of this problem. We aim to obtain optimal bounds and algorithms for the acyclic edge colouring problem on the class of subgraphs of hypercubes. We have given the best colour bound of D + 1 (where D is maximum degree of graph), for three categories of subgraphs of hypercubes. First is arbitrary subgraph of any dimensional hypercube, second is (d �� 1)-regular subgraphs of d-dimensional hypercube with constraints of limited 2 and 4 cross edges. and third is 3-regular subgraphs of any dimensional hypercube. We have given the some approaches proven effective from mathematical or simulation point of view. All the colour bounds given by us, are supported by well known, Acyclic Edge Colouring Conjecture. The approach of colouring 3-regular subgraphs of any dimensional hypercube, is not just limited to subgraphs of the hypercube, but it can also be considered for any regular bipartite graph with regularity equals to 3.