Influence of the graph density on approximate algorithms for the graph vertex coloring problem

Abstract

This research explores two heuristic algorithms designed to efficiently solve the graph coloring problem. The implementation codes for both algorithms are provided for better understanding and practical application. The experimental methodology is thoroughly discussed to ensure clarity and reproducibility. The execution times of the algorithms were measured by running the test applications six times for each analyzed graph. The results indicate that the first algorithm generally produced better solutions than the second. In only two instances did the first algorithm produce solutions comparable to those of the second. The results reveal another trend: as the graph density exceeds 85%, the number of required colors increases significantly for both algorithms. However, even at a density of 95%, the number of colors required to color the graph's vertices does not exceed half the total number of vertices. As the graph density increases from 95% to 100%, the number of colors required to color the graph rises significantly. However, when the graph density exceeds 97%, both algorithms produce identical solutions.