Total views : 215

Solving Planar Graph Coloring Problem using Enhanced Cuckoo Search


  • Department of Computer Science and Engineering, LPU, Phagwara - 144411, Punjab, India


Objectives: This paper aims towards giving colors optimally to the vertices of the graph so that graph coloring constraints can be satisfied. Methods: A hybridized algorithm that consists of Cuckoo Search along with LDO algorithm is proposed to show a comparative and more optimal algorithm for graph coloring problem. Findings: Graph coloring relates graph regions coloring in a way so that sequence of coloring will meet with all the constraints of coloring. Novelty: Hybridization of nature-inspired algorithm with Mantegna algorithm finds out the new nest positions when the nest having worst survival rate are destroyed. The Largest degree Ordering is utilized in assigning the color coding to the nodes with the nodes having the largest degree first. The experimental results prove that hybridized solution works well using moderate size and provides another approach for the same.


Degree based Ordering, Graph Coloring.

Full Text:

 |  (PDF views: 167)


  • Hsu LY, Horng SJ, Fan P, Khan MK, Wang YR, Run RS, Lai JL, Chen RJ. MTPSO algorithm for solving planar graph coloring problem. Expert Systems with Applications. 2011 May 31; 38(5):5525–31.
  • Civicioglu P, Besdok E. A conceptual comparison of the Cuckoo-search, particle swarm optimization, differential evolution and artificial bee colony algorithms. Artificial Intelligence Review. 2013 Apr 1; 39(4):315–46.
  • Vardhini KK, Sitamahalakshmi T. A Review on Naturebased Swarm Intelligence Optimization Techniques and its Current Research Directions. Indian Journal of Science and Technology. 2016 Mar 16; 9(10):1–13.
  • Mahmoudi S, Lotfi S. Modified cuckoo optimization algorithm (MCOA) to solve graph coloring problem. Applied Soft Computing. 2015 Aug 31; 33:48–64.
  • Yang XS, Deb S. Engineering optimisation by cuckoo search. International Journal of Mathematical Modelling and Numerical Optimisation. 2010 Jan 1; 1(4):330–43.
  • Bhardwaj V, Tiwari SP. Solving Planar Graph Coloring Problem Using PSO with SPV Rule. In Intelligent Computing, Networking, and Informatics Springer India.2014; 955–65.
  • Zhou Y, Zheng H, Luo Q, Wu J. An improved cuckoo search algorithm for solving planar graph coloring problem. Appl Math Inf Sci. 2013 Mar 1; 7(2):785–92.
  • Valian E, Mohanna S, Tavakoli S. Improved cuckoo search algorithm for global optimization. International Journal of Communications and Information Technology. 2011 Dec; 1(1):31–44.
  • Leccardi M. Comparison of three algorithms for Levy noise generation. In: Proceedings of Fifth EUROMECH Nonlinear Dynamics Conference. 2005.
  • San Segundo P, Lopez A, Batsyn M, Nikolaev A, Pardalos PM. Improved initial vertex ordering for exact maximum clique search. Applied Intelligence. 2016; 1–3.


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.