Influence of the graph density on approximate algorithms for the graph vertex coloring problem
Open Access
- 1 October 2025
- journal article
- Published by Institute of Advanced Engineering and Science in International Journal of Electrical and Computer Engineering (IJECE)
- Vol. 15 (5) , 4714-4722
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.Keywords
This publication has 25 references indexed in Scilit:
- On the automatic generation of metaheuristic algorithms for combinatorial optimization problemsEuropean Journal of Operational Research, 2024
- Expected polynomial-time randomized algorithm for graph coloring problemDiscrete Applied Mathematics, 2023
- On Properly Ordered Coloring of Vertices in a Vertex-Weighted GraphOrder, 2021
- Building a Maximal Independent Set for the Vertex-coloring Problem on Planar GraphsElectronic Notes in Theoretical Computer Science, 2020
- On symmetries of edge and vertex colourings of graphsDiscrete Mathematics, 2020
- Coloring graphs with no induced five‐vertex path or gemJournal of Graph Theory, 2020
- A New Vertex Coloring Heuristic and Corresponding Chromatic NumberAlgorithmica, 2020
- Polynomial Cases for the Vertex Coloring ProblemAlgorithmica, 2018
- Vertex-colouring of 3-chromatic circulant graphsDiscrete Applied Mathematics, 2017
- Some simplified NP-complete graph problemsTheoretical Computer Science, 1976