JMSS Cover
Frequency: Continuous
ISSN: 1549-3644 (Print)
ISSN: 1558-6359 (Online)
Research Article Open Access

New Graph Coloring Algorithms

Hussein Al-Omari and Khair E. Sabri

Abstract

Two new heuristic graph-coloring algorithms, based on known heuristic algorithms, have been introduced. One of them is a modification of the Largest Degree Ordering (LDO) algorithm, and the other one is a modification of the Saturation Degree Ordering (SDO) algorithm. The two new algorithms proposed in this paper, were compared empirically, in terms of used colors, with some of the known heuristic graph-coloring algorithms such as: Largest Degree Ordering (LDO), First Fit (FF), Saturated Degree Ordering (SDO), and Incident Degree Ordering (IDO). As a result of this comparison, it was found that the proposed algorithms were better than the original ones with respect to the number of used colors.

Journal of Mathematics and Statistics
Volume 2 No. 4, 2006, 439-441

DOI: https://doi.org/10.3844/jmssp.2006.439.441

Submitted On: 27 September 2006 Published On: 31 December 2007

How to Cite: Al-Omari, H. & Sabri, K. E. (2006). New Graph Coloring Algorithms. Journal of Mathematics and Statistics, 2(4), 439-441. https://doi.org/10.3844/jmssp.2006.439.441

Open AccessCopyright: © 2006 Hussein Al-Omari and Khair E. Sabri. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

  • 3,660 Views
  • 4,947 Downloads
  • 22 Citations

Download

Keywords

  • Graph coloring algorithms
  • degree ordering
  • first-fit algorithm