A Novel Edge Cover based Graph Coloring Algorithm

Graph Colouring Problem is a well-known NP-Hard problem. In Graph Colouring Problem (GCP) all vertices of any graph must be coloured in such a way that no two adjacent vertices are coloured with the same colour. In this paper, a new algorithm is proposed to solve the GCP. Proposed algorithm is based on finding vertex sets using edge cover method. In this paper implementation prospective of the algorithm is also discussed. Implemented algorithm is tested on various graph instances of DIMACS standards dataset. Algorithm execution time and a number of colours required to colour graph are compared with some other well-known Graph Colouring Algorithms. Variation in time complexity with reference to increasing in the number of vertices, a number of edges and an average degree of a graph are also discussed in this paper.

@article{Patidar2017,
  title     = {A Novel Edge Cover based Graph Coloring Algorithm},
  journal   = {International Journal of Advanced Computer Science and Applications},
  volume    = {8},
  number    = {5},
  year      = {2017},
  publisher = {The Science and Information Organization},
  author    = {Harish Patidar and Dr. Prasun Chakrabarti},
  doi       = {10.14569/IJACSA.2017.080534},
  url       = {https://doi.org/10.14569/IJACSA.2017.080534}
}