Abstract

Given an undirected graph G= (V, E), the graph coloring problem consist in assigning a color to each vertex in such a manner that two adjacent vertex have assigned different colors. The processes of assigning the colors in the graph will done in a manner such that that the total number of different colors used is minimum. Most of the existing algorithms generally deal this problem by taking consideration above constraint during assigning the color to vertices in the graph, but some time above color assignment constraints creates some other implicit constraints which increases the complexity of the algorithms. In this paper we propose an algorithm for graph coloring problem which assign the colors to vertices of the graph with minimum number of colors and without creating any other additional constraints during color assignment that required to be handled explicitly.

References

• Gamache M, Hertz A,Ouellet JO. “A graph coloring model for a feasibility problem in monthly crew scheduling with preferential bidding”. In Comput Oper Res 2007;34(8): 2384–95.
• Zufferey N, Amstutz P, Giaccari P. “Graph coloring approaches for a satellite range scheduling problem”. In J Schedul 2008;11(4):263–77.
• Werra DD. “An introduction to time tabling”. In Eur J Oper Res1985;19:151–62.
• Burke EK, McCollum B, Meisels A, Petrovic S, Qu R. “A graph based hyper heuristic for time tabling problems”. In EurJOperRes2007;176:177–92.
• Werra D D, Eisenbeis C, Lelait S, Marmol B. “On a graph theoretical model for cyclic register allocation”. In Discret Appl Math1999;93(2–3):191–203.
• Smith DH, Hurley S, Thiel SU. “Improving heuristics for the frequency assignment problem”. In Eur JOper Res1998;107(1):76–86.
• WooT K, Su SYW, Wolfe RN. “Resource allocation in a dynamically partitionable bus network using a graph coloring algorithm”. In IEEE Trans Commun 2002;39:1794–801.
• Méndez Díaz I, Zabala P. “A cutting plane algorithm for graph coloring”. In Discret Appl Math 2008;156(2):159–79.
• Lucet C, Mendes F, Moukrim A. “An exact method for graph coloring”. In Comput Oper Res 2006;33(8):2189–207.
• Méndez-Díaz I, Zabala P. “A branch-and cut algorithm for graph coloring”. In Discret Appl Math 2006;154:826–47.
• Malaguti E, Monaci M, Toth P. “An exact approach for the Vertex Coloring Problem”. In Discrete Optim 2011;8(2):174–90.
• Segundo PS. “A new DSATUR based algorithm for exact vertex coloring”. In Comput Oper Res 2012;39:1724–33.
• Chaitin GJ. “Register allocation and spilling via graph coloring”. In SIGPLAN Not 2004;39(4):66–74.
• Caramia M, DellOlmo P. “Coloring graphs by iterated local search traversing feasible and infeasible solutions”. In Discret Appl Math 2008;156(2):201–17.
• Josephine et.al “The Application of Graph Theory to Sudoku” Hang Lung Mathematics Awards Vol 6(2014) ,pp 321-349
• Charu Negi et.al “Vertex coloring problem Approach using Adjacency matrix” IJETSR vol 4 issue 12,(2017)
• Tabiya Manzoor Beigh, Girdhar Gopal . Use of Genetic Algorithm and Fuzzy Logic in Optimizing Graph Coloring Problem in IJCA Proceedings on Recent Innovations in Computer Science and Information Technology RICSIT 2016(1):1-4, September 2016.
• Zhaoyang Zhou, Chu-Min Li, Chong Huang, Ruchu Xu An exact algorithm with learning for the graph coloring problem Computers & Operation Research 51(2014)282-301