Greedy and Grasp Algorithms for Total Coloring of Graphs

The aim of this thesis is to study computational approaches to the total coloring problem in graph theory. Total coloring assigns colors to both vertices and edges of a graph such that no adjacent or incident elements share the same color. Since the total coloring problem is NP-hard, exact methods are not practical for large graphs. In this thesis, two algorithmic approaches are implemented and compared. First, greedy heuristics are implemented that construct total colorings using different vertex and edge ordering criteria. Second, a GRASP ( Greedy Randomized Adaptive Search Procedure) is implemented that improves greedy solutions through randomized construction and local search. Both approaches are tested on a diverse set of graph families. Experimental results are discussed and the performance of the proposed algorithms is compared.