International Journal of Electrical and Computer Engineering (IJECE) Vol.
No.
October 2025, pp.
ISSN: 2088-8708.
DOI: 10.
11591/ijece.
Influence of the graph density on approximate algorithms for the graph vertex coloring problem Velin Kralev.
Radoslava Kraleva Department of Informatics.
South-West University AuNeofit RilskiAy.
Blagoevgrad.
Bulgaria
Article Info
ABSTRACT
Article history:
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 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 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.
Received Aug 14, 2024 Revised Apr 14, 2025 Accepted Jul 3, 2025 Keywords:
Chromatic number Graph coloring Graph density Graph theory Greedy algorithm This is an open access article under the CC BY-SA license.
Corresponding Author:
Velin Kralev Department of Informatics.
Faculty of Mathematics and Natural Science.
South-West University 66 Ivan Michailov str.
, 2700 Blagoevgrad.
Bulgaria Email: velin_kralev@swu.
INTRODUCTION
Informally, the labeling .
r colorin.
of a graph's vertices can be described as assigning each vertex a specific label .
r colo.
The goal of this process is to assign labels .
such that no two adjacent vertices share the same label .
The labels .
r color.
assigned to the vertices are elements of a finite set, with each vertex receiving exactly one of these elements.
A collection of vertices assigned the same label .
is known as a chromatic .
r colo.
If c-number sets are formed, i.
, classes can define a graph as c-colorable.
Natural numbers from 1 through c are usually used to denote these chromatic classes.
For a graph coloring to be valid, every pair of adjacent vertices .
, vertices connected by an edg.
must be assigned different labels .
Formally and in general, it can be defined that when a graph is colored acceptably .
for example with c colors, then it is c-colorable.
An acceptable coloring of a graph always exists.
If a graph has n vertices, each vertex can be assigned a unique color, resulting in exactly n chromatic classes.
This will certainly be an acceptable labeling .
r colorin.
of the given graph.
With this coloring scheme, no two vertices will share the same label .
r colo.
, regardless of whether they are connected by an edge .
, .
The smallest possible number of chromatic classes in which the vertices of a given graph can be distributed is called the optimal coloring of the graph and is denoted by N(G).
If a graph is not complete then N(G) is certainly less than the number of vertices of the given graph, i.
N(G) < n.
If it is found that for a Journal homepage: http://ijece.
Int J Elec & Comp Eng
ISSN: 2088-8708
graph G.
N(G)=c, then this graph is c-chromatic.
The correct .
coloring of a c-color graph is the grouping of the vertices of that graph into c sets, the vertices in each of these sets being unrelated to each other but may be .
nd usually ar.
connected vertices of different sets.
If graph G' is a subgraph of a graph G, then any acceptable coloring of the graph G will also be an acceptable coloring of the graph G'.
Moreover, the chromatic index of a graph G' is less than or at most equal to the chromatic index of a graph G .
, .
The problem of labeling .
n the field of graph theor.
is an NP-hard problem .
and is still actively studied .
Ae.
Various approaches, methods, and algorithms for solving this problem continue to be actively researched in scientific literature.
For instance, the maximal independent set for the vertex-coloring problem on planar graphs .
, the adjacent vertex-distinguishing edge coloring .
, the rainbow vertex coloring problem .
, and many others.
Different methods of the problem use various algorithms .
, .
, approaches .
Ae.
and techniques .
, .
Other methods are used to find a solution to such problems in the field of graph theory .
Many other more detailed and in-depth analyzes of this problem are discussed in .
Ae.
Any complete graph that does not contain parallel edges and loops can be colored with exactly |V| of number of colors, where |V| is the number of vertices in this graph.
This is because in every complete graph for every pair of vertices there is an edge that connects these vertices.
Also, in every complete graph, every vertex is connected .
y an edg.
to every other vertex.
Therefore, the chromatic index of any complete graph is equal to the number of vertices in that graph.
Because of this statement, it can be concluded that if a graph has its complete subgraph, then the chromatic index of this graph will be at least equal .
r greate.
to the number of vertices that form the complete subgraph in the given graph.
It is also known that in each graph that has its complete subgraph, it is possible for the chromatic index of this graph to be greater .
ut not les.
than the number of vertices forming the complete subgraph .
In this paper, some results obtained after the execution of two modified versions of the greedy algorithm used to solve the problem of labeling .
the vertices of a graph Ae Greedy coloring algorithm (GCA) .
are presented and analyzed.
The first version of the greedy algorithm is classical and the initial arrangement of the vertices does not change when it is executed.
With this modification, the vertices are labeled .
in the order in which they were added to the graph - i.
, by index .
reedy coloring algorithm based on the index ordering Ae GC-IDX).
The second variant of the greedy algorithm is implemented as the initial order of the vertices is changed, but in a random arrangement way, i.
a random arrangement of vertices is generated, one from all possible ones .
hich are exactly n!).
After this step, the vertices of the graph are labeled .
according to the generated order of vertices Ae i.
, randomly .
reedy coloring algorithm based on the random ordering - GC-RND).
Both variants of the greedy algorithm are approximate, and thus, it is not guaranteed that either modification will find the optimal solution for labeling .
the graph's vertices using the fewest labels .
When solving NP-hard problems with large input data, only approximate algorithms can be used, since they can generate at least a close to the optimal solution and at an acceptable time, for example in the order of seconds to few minutes.
Other algorithms for solving specific variants of the graph vertex labeling .
problem are also known and discussed in other publications .
, .
RESEARCH METHOD
This section shows and discusses the source codes of both algorithms GC-IDX and GC-RND Both algorithms are approximate and solve the graph vertex coloring problem approximately.
For both algorithms Ae GC-IDX and GC-RND, some parameters, dynamic arrays and matrices need to be declared in advance.
They are presented in Figure 1.
01 var 02 iC NumberOfVertices: Integer.
03 iC ArrayOfColors: array of TColor.
04 iC MinimalColors.
RandomCount: Integer.
05 iC BestMinimalColors.
BestIteration: Integer.
06 iC AdjacencyMatrix: array of array of Integer.
Figure 1.
Source code of preliminary declarations The NumberOfVertices parameter stores the number of vertices in the graph.
The ArrayOfColors array is used by both algorithms.
Each item of this dynamic structure contains an item of type TColor with which the given vertex of the graph is colored.
Both algorithms (CG-IDX and CG-RND) change the values Influence of the graph density on approximate algorithms for A (Velin Krale.
A ISSN: 2088-8708 of these items.
The MinimalColors parameter is aggregated and is used by the algorithms in the solution search loop.
Each graph is represented by an adjacency matrix .
, which is used by both algorithms.
Each item .
, .
of the matrix shows whether vertices with indices u and v are adjacent or not.
The GreedyColoringIDX procedure implements the first approximate method for labeling .
graph vertices.
The source code of this procedure is shown in Figure 2.
This procedure also uses some additional parameters Ae CurrentColor.
Vertex and AcceptableSolution.
The CurrentColor parameter holds the number of one of the colors used.
Parameter V is used when iterating the adjacency matrix when searching for the neighbors of the given vertex.
The AcceptableSolution parameter indicates whether the given vertex has been successfully colored with any of the available colors.
01 procedure GreedyColoringIDX.
02 begin 03 iC var AcceptableSolution: Boolean := False.
04 iC var V := 0.
var Vertex := 0.
var CurrentColor := 0.
05 iC MinimalColors := 0.
06 iC for Vertex := 1 to NumberOfVertices do 07 iC begin 08 iC iC CurrentColor := 0.
09 iC iC while not AcceptableSolution do 10 iC iC begin 11 iC iC iC CurrentColor := CurrentColor 1.
12 iC iC iC AcceptableSolution := True.
13 iC iC iC for V := 1 to NumberOfVertices do 14 iC iC iC begin 15 iC iC iC iC if ((AdjacencyMatrix[Verte.
[V] > .
and 16 iC iC iC iC (ArrayOfColors[V]=CurrentColo.
) then 17 iC iC iC iC begin 18 iC iC iC iC iC AcceptableSolution := False.
19 iC iC iC iC iC Break.
20 iC iC iC iC end.
21 iC iC iC end.
22 iC iC end.
23 iC iC ArrayOfColors[Verte.
:= CurrentColor.
24 iC iC if (MinimalColors < CurrentColo.
then 25 iC iC MinimalColors := CurrentColor.
26 iC end.
27 end.
Figure 2.
Source code of the GreedyColoringIDX procedure The parameters MinimalColors.
Vertex and CurrentColor are set to 0 in the beginning of the GreedyColoringIDX procedure .
ows 4 and .
The procedure checks which of the current colors can be used to color the given vertex .
hrough a for-loop started on row .
Finding the color with the smallest possible index to be used for coloring is realized by a while-loop .
ows 09 - .
Just before the execution of the loop, the CurrentColor parameter is set to 0 .
In line 11, the CurrentColor parameter is incremented by 1, which means that on the first iteration of the loop, this parameter will be set to 1.
Through the for loop .
xecuted between rows 11-.
, it is checked whether any of the neighboring .
vertices of the current vertex .
arameter Verte.
is not already colored with the color CurrentColor.
If this is not the case, then the current vertex is colored with CurrentColor.
The execution of the for loop can be prematurely terminated if a vertex which is adjacent to the current one and is already colored with the CurrentColor is If this happens, the AcceptableSolution parameter is set to False before the loop is terminated.
In this situation, the coloring of the current vertex with the CurrentColor is impossible, and the procedure executes a new iteration of the while loop and increasing the index of the current color by 1 .
Execution of the while loop .
ows 09 - .
continues until an acceptable .
color is found for the current vertex.
In this case, the parameter AcceptableSolution will be set to True .
n row 12 before starting the for loo.
The value of the CurrentColor parameter is stored in the array ArrayOfColors in the item associated with the parameter Vertex .
The value of the CurrentColor parameter is copied to the MinimalColors parameter only if the value of the CurrentColor parameter is greater than the value of the MinimalColors parameter.
When the value of the MinimalColors parameter is increased by one, it means that the available colors are not enough to color the current vertex and a new color needs to be added, which is done by increasing by one the value of the MinimalColors parameter.
The execution of the for loop .
ines 06 Ae .
ends only when all the vertices in the graph are colored, and in such a way that no pair of adjacent vertices Int J Elec & Comp Eng.
Vol.
No.
October 2025: 4714-4722
Int J Elec & Comp Eng
ISSN: 2088-8708
are colored with the same color.
After the execution of the GreedyColoringIDX procedure, the MinimalColors parameter stores the minimum number of colors needed to color the given graph, according to the implementation of the algorithm constructed in this way.
The GreedyColoringRND procedure implements the second approximate method for coloring graph The source code of this procedure is shown in Figure 3.
This procedure also uses some additional parameters Ae BestMinimalColors.
BestIteration and RandomCount.
The BestMinimalColors parameter holds the minimal number of colors needed to color the graph vertices.
This parameter has a different purpose than the MinimalColors parameter, which contains the minimum number of colors required when running the current GreedyColoringIDX procedure.
In contrast to this parameter, the BestMinimalColors parameter contains the minimum number of colors to color the graph after executing several GreedyColoringIDX In contrast to this parameter, the BestMinimalColors parameter contains the minimum number of colors to color the graph after running the GreedyColoringIDX procedure several times.
The number of these calls is determined by the RandomCount parameter, which is initialized when the GreedyColoringRND procedure is started.
Accordingly, the BestIteration parameter stores which call the GreedyColoringIDX procedure found the best solution, information about which is stored in the BestMinimalColors parameter.
The essence of the GreedyColoringRND procedure consists in the successive generation of different .
permutations of the vertices of the graph, based on which, in the next step, these vertices will be colored according to this order by the GreedyColoringIDX procedure.
The random order of the vertices is generated by the for loop .
ines 07 Ae .
, starting from the last vertex for which a new index of another vertex is chosen .
with which the current one is exchanged .
In the next step, a new .
index is chosen for the penultimate vertex, which is exchanged with some vertex from those before it.
This process is repeated until all vertices up to the first have been randomly swapped.
After the new order is generated, the procedure GreedyColoringIDX is called, which colors the vertices of the graph in the thus generated suborder.
When the GreedyColoringIDX procedure is executed, the number of colors needed to color all vertices of the graph is calculated.
This count is stored in the MinimalColors parameter, which is compared to the best solution found from a previous iteration of the algorithm.
If the current solution is better .
the MinimalColors parameter has a smaller value than the BestMinimalColors paramete.
then the current solution is stored as the best found so far.
Accordingly, the BestIteration parameter stores the iteration at which this .
solution was found.
01 procedure GreedyColoringRND.
02 begin 03 iC BestMinimalColors := MaxInt.
RandomCount := 100.
04 iC BestIteration := 0.
05 iC for var Iteration := 1 to RandomCount do 06 iC begin 07 iC iC for var V := NumberOfVertices downto 1 do 08 iC iC begin 09 iC iC iC var I := V.
10 iC iC iC var J := Random(V) 1.
11 iC iC iC var T := I.
I := J.
J := T.
// Swap vertices I and J 12 iC iC end.
13 iC iC GreedyColoringIDX().
14 iC iC if MinimalColors < BestMinimalColors then 15 iC iC begin 16 iC iC iC BestMinimalColors := MinimalColors.
17 iC iC iC BestIteration := Iteration.
18 iC iC end.
19 iC end.
20 end.
Figure 3.
Source code of the GreedyColoringRND procedure RESULTS AND DISCUSSION The results of the experiment will be presented.
An analysis between the two approximate methods will also be presented in terms of the number of minimum colors required to color the test graphs, as well as the running time of the algorithms.
For this study, 24 graphs with 1000 vertices and different numbers of edges were created.
These graphs are undirected and contain no multi-edges .
arallel edges or multiple edge.
or loops.
The number of edges is determined by the graph density .
n percentag.
that is set for each This parameter ranges from 5 to 95 for graphs G1 Ae G19 and changes in 5 percent increments.
For graphs G20 Ae G24 this parameter ranges from 96 to 100 and changes in 1 percent increments.
Influence of the graph density on approximate algorithms for A (Velin Krale.
A ISSN: 2088-8708 Each graph contains the same number of vertices .
The maximum possible number of edges that a graph with 1000 vertices can contain .
ithout parallel edges and loop.
is 1000*.
/2=499500.
From these edges, a certain percentage of them is randomly selected based on the graph density parameter.
Additional information about the test graphs and the results of the execution of the two algorithms are shown in Tables 1 and 2.
The experimental conditions are: 64-bit Win 11 OS and hardware configuration:
Processor: Intel (R) Core (TM) i5-12450H at 4.
40 GHz.
RAM: 16 GB.
SSD 1000 GB.
Table 1.
Results of the approximate algorithms for graphs G1 Ae G19
Graph
Graph
file name
G_1000_24976
G_1000_49950
G_1000_74926
G_1000_99900
G_1000_124876
G_1000_149850
G_1000_174826
G_1000_199800
G_1000_224776
G_1000_249750
G_1000_274726
G_1000_299700
G_1000_324676
G_1000_349650
G_1000_374626
G_1000_399600
G_1000_424576
G_1000_449550
G_1000_474526
Graph
Graph
file name
G_1000_479520
G_1000_484516
G_1000_489510
G_1000_494506
G_1000_499500
Density (%) Edges .
Greedy Coloring (IDX) Colors Time .
Greedy Coloring (RND) Colors Time .
Iteration Diff in Table 2.
Results of the approximate algorithms for graphs G20 Ae G24 Density (%) Edges .
Greedy Coloring (IDX) Colors Time .
Greedy Coloring (RND) Colors Time .
Iteration Diff in In Tables 1 and 2, the AuGraph numberAy column shows the number of the test graph.
The AuGraph file nameAy column shows the name of the file where the information for the corresponding test graph is stored.
The AuDensity (%)Ay column shows the density of the test graph in terms of the number of edges that this graph contains out of all the possible edges that this graph would have if it were complete.
Accordingly, the column AuEdge countAy shows the number of these edges.
The AuColorAy columns show the number of required colors that each of the algorithms used to color the corresponding graph.
Accordingly, the AuTime .
Ay columns show the time for each of the two algorithms to generate a solution.
The AuIterationAy column shows the best iteration of the GC-RND algorithm where the algorithm generated the best solution out of a total of 250 iterations performed.
The AuDiff in colorsAy column shows the difference in chromatic classes between the GCRND algorithm and the CG-IDX algorithm.
Table 1 and the charts in Figures 4 and 5 show the results of the two algorithms in terms of the number of required colors that the two algorithms used to color the graphs from G1 through G19.
The results also show that for all nineteen graphs from G1 through G19, the GC-IDX algorithm found better solutions than the GC-RND algorithm.
In two cases, only the number of chromatic classes .
generated by the GC-RND algorithm are close to those generated by the GC-IDX algorithm Ae these are the cases for graphs G14 and G17.
For graph G14, the GC-IDX algorithm generated a solution where 174 colors were needed to color the graph.
Accordingly, the GC-RND algorithm found a very close solution, where 175 colors were needed to color the graph .
, only one color more than the colors the GC-IDX algorithm use.
In all other cases, the GC-IDX algorithm found solutions that were better than those found by the GC-RND algorithm.
The difference in the number of colors varies between 4 and 12, with graphs G1 and G16 having a difference of 4 colors and graph G13 having a difference of 12 colors as shown in Figure 5.
However.
Figures 4 and 5 show that as the number of edges in the graph increases, which is a consequence of the graph density Int J Elec & Comp Eng.
Vol.
No.
October 2025: 4714-4722
Int J Elec & Comp Eng
ISSN: 2088-8708
increasing, the GC-RND algorithm begins to generate solutions that are closer to those generated by GC-IDX From the trend of the obtained results, it can be concluded that for graphs with a higher density, for example greater than 70%, the GC-RND algorithm can be successfully used to generate solutions.
Figure 4.
The number of colors .
eft y-axi.
generated by the two algorithms at different graph densities .
ight y-axi.
Figure 5.
Difference in chromatic classes between the GC (RND) algorithm and the CG (IDX) algorithm The chart in Figure 4 shows another trend, which is related to the number of required colors that the two algorithms used in finding a solution.
When increasing the density of the graph, for example for values greater than 85%, the number of required colors increases significantly, and this is true for both algorithms GC-IDX algorithm and GC-RND algorithm.
However, the number of colors needed to color the vertices of a graph, even at a density of 95% does not exceed more than half the number of vertices in the same graph, since 394/1000=0.
This is an important result of how increasing the density of the graph affects the number of chromatic classes generated by the algorithms.
It is known that for a complete graph, i.
, at 100% density, the number of colors required to color a graph equal to the number of vertices of that graph.
This means that when the density of the graph changes between 95% and 100%, the number of colors needed to color the graph increases significantly.
This is exactly what the results presented in Table 2.
It can also be seen that at high values of the graph density parameter, both algorithms generate identical solutions, such as the results obtained for graphs with density above 97%.
The chart in Figure 6 illustrates how increasing the number of edges .
nd thus the graph densit.
impacts the execution time of the two algorithms.
The execution time of the GC-RND algorithm is Influence of the graph density on approximate algorithms for A (Velin Krale.
A ISSN: 2088-8708 significantly longer than that of the GC-IDX algorithm.
This difference varies: for example, in graph G1, which has the lowest density, the difference is the largest, while in graph G19, which has the highest density, the difference is the smallest.
However, for each run of the GC-RND algorithm, 100 iterations are performed, and the iteration that generates the best solution is selected.
The times presented in Table 1 include the execution time of all 100 iterations.
This means that the actual time for a single execution of the algorithm is, on average, 100 times less.
The complexity of both algorithms is quadratic, primarily depending on the number of vertices in the graph, and to a lesser extent on its density, i.
, the number of edges.
This is illustrated in Figure 6, where a significant increase in the number of edges, and thus the graph's density, results in the execution time of both algorithms changing insignificantly and linearly, with only a very small Figure 6.
Comparison of the execution times of both algorithms CONCLUSION This paper discusses a study related to the graph labeling .
Various scientific analyses, methods, and algorithms related to the graph labeling .
problem were discussed.
In this paper, two approximate algorithms for solving the graph vertex coloring problem were implemented and The declarations of the basic data structures used by the algorithms, including one-dimensional and two-dimensional arrays, were also presented.
The program codes of both heuristic algorithms were presented and analyzed in detail.
When conducting the experiments, the operating system's ability to work in multitasking mode was specifically considered.
Accordingly, six runs of both algorithms were conducted for each of the 24 analyzed graphs.
The average execution times from these runs were calculated and presented in Tables 1 and 2.
For the solutions generated by the GC-IDX algorithm, identical results were obtained in all These results are also presented in Table 1 and Table 2.
In contrast, the GC-RND algorithm produced different results across the six runs.
Table 1 and Table 2 present the best results generated for each graph across all runs.
The results of this experiment show that, for graphs G1 Ae G19, the GC-IDX algorithm generated better solutions than those generated by the GC-RND algorithm in most cases.
In only two cases did the GCRND algorithm generate solutions that were comparable to those produced by the GC-IDX algorithm.
The results indicate 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 vertices of a graph does not exceed half the number of vertices in the graph.
This is an important finding that demonstrates how increasing the graph's density affects the number of chromatic classes generated by the algorithms.
As the graph density increases from 95% to 100%, the number of colors required to color the graph rises significantly.
However, for graph density values above 97%, both algorithms generate identical The complexity of both algorithms is quadratic, primarily depending on the number of vertices in the graph and, to a lesser extent, on its density, i.
, the number of edges.
The results indicate that with a significant increase in graph density, i.
, a substantial increase in the number of edges, the execution time of both algorithms changes insignificantly and almost linearly, with only a very small increment.
Int J Elec & Comp Eng.
Vol.
No.
October 2025: 4714-4722
Int J Elec & Comp Eng
ISSN: 2088-8708
FUNDING INFORMATION
This research was conducted without financial support from external sources.
AUTHOR CONTRIBUTIONS STATEMENT
This journal uses the Contributor Roles Taxonomy (CRediT) to recognize individual author contributions, reduce authorship disputes, and facilitate collaboration.
Name of Author Velin Kralev Radoslava Kraleva C : Conceptualization M : Methodology So : Software Va : Validation Fo : Formal analysis ue ue ue ue ue ue ue ue ue ue I : Investigation R : Resources D : Data Curation O : Writing - Original Draft E : Writing - Review & Editing ue ue ue ue ue ue ue ue ue ue ue Vi : Visualization Su : Supervision P : Project administration Fu : Funding acquisition CONFLICT OF INTEREST STATEMENT Authors state no conflict of interest.
DATA AVAILABILITY
The data that support the findings of this study are available from the corresponding author.
VK, upon reasonable request.
REFERENCES