Complementary Graph Coloring

Authors

  • Mohamed Al-Ibrahim Computing Department, KILAW, Doha, Kuwait
  • Naser Al-Ibrahim Computer Engineering Department, Kuwait University, Khaldyia, Kuwait
  • Yousef Rafique Computer Engineering Department, Kuwait University, Khaldyia, Kuwait
  • Omar Al-Sumait Computer Engineering Department, Kuwait University, Khaldyia, Kuwait

Keywords:

Graph Coloring, Complementary Graphs, Chromatic Number.

Abstract

The objective of the Graph Coloring problem is to color vertices of a graph in such a way that no two vertices that share an edge are assigned the same color. Aircraft Scheduling, Frequency Assignment, register allocation are all real life applications that can be solved using graph coloring. Graph Coloring is a well-known NP-complete problem to the academia in computer science and mathematics. In this paper we use the concept of complementary graphs to come up with a new heuristic for graph coloring. Our results are compared with an exact algorithm and other heuristic algorithms to evaluate our algorithm’s performance. 

References

D. Br ́elaz. New methods to color the vertices of a graph. Communications of the ACM, 22(4):251–256, 1979.

M. R. Garey and D. S. Johnson. Computers and intractibility: a guide to the theory of np-completeness. WH Freeman and Company, New York, 18:41, 1979.

M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified np-complete problems. In Proceedings of the sixth annual ACM symposium on Theory of computing, pages 47–63. ACM, 1974.

E. L. Lawler. A note on the complexity of the chromatic number problem. Information Processing Letters, 5(3):66–67, 1976.

P. San Segundo. A new dsatur-based algorithm for exact vertex coloring. Computers & Operations Research, 39(7):1724–1733, 2012.

E. Sewell. An improved algorithm for exact graph coloring. DIMACS series in discrete mathematics and theoretical computer science, 26:359–373, 1996.

G. M. Slota, S. Rajamanickam, and K. Madduri. Bfs and coloring-based parallel algorithms for strongly connected components and related problems. In IEEE International Parallel and Distributed Processing Symposium, 2014.

D. J. Welsh and M. B. Powell. An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal, 10(1):85–86, 1967.

Downloads

Published

2016-11-09

How to Cite

Al-Ibrahim, M., Al-Ibrahim, N., Rafique, Y., & Al-Sumait, O. (2016). Complementary Graph Coloring. International Journal of Computer (IJC), 23(1), 42–52. Retrieved from https://ijcjournal.org/index.php/InternationalJournalOfComputer/article/view/736

Issue

Vol. 23 No. 1 (2016)

Section

Articles

License

Authors who submit papers with this journal agree to the following terms.