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

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...