<![CDATA[This study compares three graph coloring algorithms (Greedy, Welch–Powell (WP), and Marble–Matula–Isaacson (MMI)) applied to geometric mosaic images in the form of undirected graphs. Each vertex represents a region in the image, while edges connect neighboring regions. Two graphs are used as research objects, namely graph (a) with |V(GA)| = 56, |E(GA)| = 96, D(GA) = 0.062234, δ(GA) = 2, Δ(GA) = 7, and graph (b) with |V(GB)| = 55, |E(GB)| = 115, D(GB) = 0.0174, δ(GB) = 3, Δ(GB) = 6. The three algorithms are tested through 15 experiments to minimize the number of colors so that no two neighboring vertices have the same color. The Wilcoxon Rank-Sign statistical test shows that WP and MMI are significantly more efficient than Greedy, with p-values of 0.0006269 and 0.01073 (<0.05), respectively. The theoretical reason why the Greedy algorithm is not optimal compared to the other two algorithms is because the Greedy algorithm colors the vertices according to the input order without a vertex selection strategy based on degree or graph structure. These results confirm that WP and MMI are able to approach the theoretical limit of planar graph coloring as stated by the Four Color Theorem, which states that every planar graph can be colored with no more than four colors.]]>
Copyrights © 2025
