Future of Information and Communication Conference (FICC) 2024
4-5 April 2024
Publication Links
IJACSA
Special Issues
Future of Information and Communication Conference (FICC)
Computing Conference
Intelligent Systems Conference (IntelliSys)
Future Technologies Conference (FTC)
International Journal of Advanced Computer Science and Applications(IJACSA), Volume 8 Issue 5, 2017.
Abstract: 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.
Harish Patidar and Dr. Prasun Chakrabarti, “A Novel Edge Cover based Graph Coloring Algorithm” International Journal of Advanced Computer Science and Applications(IJACSA), 8(5), 2017. http://dx.doi.org/10.14569/IJACSA.2017.080534
@article{Patidar2017,
title = {A Novel Edge Cover based Graph Coloring Algorithm},
journal = {International Journal of Advanced Computer Science and Applications},
doi = {10.14569/IJACSA.2017.080534},
url = {http://dx.doi.org/10.14569/IJACSA.2017.080534},
year = {2017},
publisher = {The Science and Information Organization},
volume = {8},
number = {5},
author = {Harish Patidar and Dr. Prasun Chakrabarti}
}
Copyright Statement: This is an open access article licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, even commercially as long as the original work is properly cited.