## Acyclic Edge Coloring of Complete Graphs

The acyclic edge colouring problem for a given graph G asks for an
edge colouring that does not induce any bi-chromatic cycles.
Determining the least number of colours required to acyclically
edge colour a graph is a hard problem both from a theoretical and
algorithmic point of view. Algorithms for only a few special cases
are known.
As part of this project, we would like to study the edge colouring
problem for complete graphs. We approach this problem along two
fronts. One approach is to extend the acyclic edge colouring for
complete graphs on prime number of vertices to complete graphs of
a given size via a suitably designed product operation. Another
approach is to study the perfect 1-factorization conjecture for
complete graphs that would also yield an acyclic edge colouring
of complete graphs using the optimal number of colours.

The primary outcome of this project is to arrive at efficient
algorithms for acyclically edge colouring complete graphs.
Additionally, we would also like to show that our algorithms are
efficient not only in theory but also in practice.

The project is funded by the Department of Science and
Technology, Government of India for three years, 2008--11.

Other related problems that are being addressed are in the
area of graph labeling. We studied cordial labelings, and
vertex magic total labelings.

## People

- V. Ch. Venkaiah
- Kishore Kothapalli
- Kishore Yadav
- Satish Varagani
- Bharat Joshi
- K. Ramanjaneyulu
- H. K. Krishnappa

## Publications

K. Ramanjaneyulu, V. Ch. Venkaiah and ** Kishore Kothapalli**.
Cordial labelings of a Class of Planar Graphs,
AKCE Journal of Graphs and Combinatorics, 6, No. 1 (2009), pp. 171-181.
H. K. Krishnappa, ** Kishore Kothapalli**, and V. Ch. Venkaiah.
Vertex Magic Total Labelings of Complete Graphs,
AKCE Journal of Graphs and Combinatorics, 6, No. 1 (2009), pp. 143-154.
K. Ramanjaneyulu, ** K. Kothapalli **, V. Ch. Venkaiah.
Cordial Labeling of a Class of Planar Graphs, in Proc. of the
International Workshop on Graph Labeling, 2009.
H. K. Krishnappa, ** K. Kothapalli**, V. Ch. Venkaiah.
Vertex Magic Total Labeling of Complete Graphs in Proc. of the
International Workshop on Graph Labeling, 2009.
K. Kothapalli, V. Ch. Venkaiah, B. Joshi, and K.
Ramanjaneyulu, Acyclic Edge
Coloring of Kp(q-1), Kp(q-1)(r-1), and
K(p-1)(q-1),(p-1)(q-1) in International Conference on
Graph Theory and its Applications, 2009.
K. Kothapalli, V. Ch. Venkaiah, Kishore Yadav, and
Satish Varagani. Acyclic
Vertex Coloring of Graphs of Maximum Degree 5 , in
International Conference on Graph Theory and its Applications,
2009.
K. Kothapalli, V. Ch. Venkaiah, K. Ramanjaneyulu. Cordial Labeling of a Class of
Planar Graphs, in Proc. of the International Workshop
on Graph Labeling, 2009.
K. Kothapalli, V. Ch. Venkaiah, H. K. Krishnappa. Vertex Magic Total Labeling of
Complete Graphs in Proc. of the International Workshop
on Graph Labeling, 2009.
K. Kothapalli, V. Ch. Venkaiah, and K. Ramanjaneyulu,
Anti-magic Labellings for a class of
Planar Graphs, the Australasian Journal of Combinatorics, 2008.
## Software

Coming soon...