A heuristic algorithm for the set T-coloring problem

摘要

Graph theory is a convenient mathematical tool, which can be, used to model, as visual representations, problems that arise in various scientific fields and in real life practical problems. One of the most outstanding concepts in graph theory is the notion of graph coloring. A coloring of a graph G=(V, E) is an assignment of colors to its nodes so that no two adjacent nodes have the same color. A coloring of G with k colors is a k-coloring. The nodes that are assigned the same color are independent and they form a color class. The smallest k for which G has a k-coloring is the chromatic number /spl chi/(G). The k-coloring of an arbitrary graph G is NP-complete, while the determination of the chromatic number is NP-hard. We develop a heuristic algorithm, called STC that uses greedy techniques so as to find an approximate value of the D-set-T-chromatic number /spl chi//sub DT/(G).