From Graph Theory to Computational Thinking: Performance Trade-Offs in Graph Coloring Algorithms
DOI:
https://doi.org/10.61987/edulearn.v1i1.56Keywords:
Graph Coloring, Algorithm Performance, Computational EfficiencyAbstract
Graph coloring is an important topic in graph theory with applications in scheduling, traffic management, network optimization, and other conflict-avoidance problems. This study aims to compare the performance of the Greedy, Welch–Powell, and Sequential algorithms in terms of computational time and the number of colors used across graphs with different sizes and structures. A quantitative comparative approach was employed using graph datasets obtained from open sources. The datasets were represented as adjacency matrices and processed using the three graph coloring algorithms under a consistent computational procedure. The results show that the Greedy and Welch–Powell algorithms produced the same number of colors for most datasets, while the Greedy algorithm generally required the least computational time. For larger graphs, the Greedy and Welch–Powell algorithms produced fewer colors than the Sequential algorithm in some cases. The Sequential algorithm demonstrated relatively fast execution but tended to require more colors, whereas the Welch–Powell algorithm achieved competitive coloring results with greater computational time. These findings imply that algorithm selection should consider both coloring quality and computational efficiency. The comparative framework also has educational implications by supporting algorithmic thinking, computational thinking, and evidence-based problem-solving in graph theory learning.
References
Angkhanawin, T., Deger, A., Pritchard, J., & Adams, C. (2025). Graph Coloring via Quantum Optimization on a Rydberg-Qudit Atom Array. Quantum Science and Technology, 11. https://doi.org/10.1088/2058-9565/ae3b6d
Antoniadis, A., Broersma, H., & Meng, Y. (2026). Incorporating Predictions in Online Graph Coloring Algorithms. Discrete Applied Mathematics, 379, 434–445. https://doi.org/10.1016/j.dam.2025.08.063
Asgarli, S., Krehbiel, S., & Levinson, H. (2025). Coloring Graphs as Complete Graph Invariants. Discrete Mathematics, 349, Article 115245.
Bai, X., Li, B., Xu, C., & Zhang, X. (2023). Cooperative Coloring of Some Graph Families. Discrete Mathematics, 347, Article 113973.
Brighen, A., Slimani, H., Rezgui, A., & Kheddouci, H. (2023). A New Distributed Graph Coloring Algorithm for Large Graphs. Cluster Computing, 27, 875–891. https://doi.org/10.1007/s10586-023-03988-x
Crombez, L., Fonseca, G., Fontan, F., Gérard, Y., Gonzalez-Lorenzo, A., Lafourcade, P., … Zheng, D. (2023). Conflict Optimization for Binary CSP Applied to Minimum Partition into Plane Subgraphs and Graph Coloring. ACM Journal of Experimental Algorithmics, 28, 1–13. https://doi.org/10.1145/3588869
D’Ascenzo, A., D’Emidio, M., Flammini, M., & Monaco, G. (2024). Digraph k-Coloring Games: New Algorithms and Experiments. Journal of Artificial Intelligence Research, 81, 163–202. https://doi.org/10.1613/jair.1.16174
Deeds, K., Sabale, D., Kayali, M., & Suciu, D. (2024). COLOR: A Framework for Applying Graph Coloring to Subgraph Cardinality Estimation. Proceedings of the VLDB Endowment, 18, 130–143. https://doi.org/10.14778/3705829.3705834
Faiqoh, N., & Farisi, O. I. R. (2024). Application of Graph Coloring in Learning Schedule Arrangement at MAN 1 Probolinggo. Nusantara Journal of Computers and Its Application, 9.
Farisi, O. (2023). Teori Graf dan Aplikasinya (Vol. 222). Pustaka Nurja.
Feghali, C., Le, H.-O., & Le, V. B. (2025). The Parameterized Complexity of Strong Conflict-Free Vertex-Connection Colorability. https://doi.org/10.1016/j.dam.2025.12.025
Gao, M., & Hu, J. (2024). Graph Coloring Algorithm Based on Minimal Cost Graph Neural Network. IEEE Access, 12, 168000–168009. https://doi.org/10.1109/ACCESS.2024.3439352
Haviv, I., & Rabinovich, D. (2025). A Near-Optimal Kernel for a Coloring Problem. Discrete Applied Mathematics, 377, 66–73.
Kattemölle, J. (2024). Edge Coloring Lattice Graphs. arXiv. https://doi.org/10.48550/arXiv.2402.08752
Maus, Y. (2023). Distributed Graph Coloring Made Easy. ACM Transactions on Parallel Computing, 10, 1–21. https://doi.org/10.1145/3605896
Meng, L., Shao, Y., Yuan, L., Lai, L., Cheng, P., Li, X., … Zhou, J. (2024). A Survey of Distributed Graph Algorithms on Massive Graphs. ACM Computing Surveys, 57, 1–39. https://doi.org/10.1145/3694966
Mobarsa, D., Shukla, M., Maheta, N., Sata, A., & Jarboui, S. (2025). Novel Representation of Complexity of Investment Casting Using Injective Coloring and Graph Adaptive Consensus Mechanism. Scientific Reports, 15. https://doi.org/10.1038/s41598-025-27113-7
Rahman, A., Dufresne, Y., & Medvedev, P. (2024). Compression Algorithm for Colored de Bruijn Graphs. Algorithms for Molecular Biology, 19. https://doi.org/10.1186/s13015-024-00254-6
Saad, R. (2024). Parallel Connectivity in Edge-Colored Complete Graphs: Complexity Results. Graphs and Combinatorics, 40. https://doi.org/10.1007/s00373-023-02747-4
Schidler, A., & Szeider, S. (2023). SAT-Boosted Tabu Search for Coloring Massive Graphs. ACM Journal of Experimental Algorithmics, 28, 1–19. https://doi.org/10.1145/3603112
Shen, Y., Li, X., Yuan, T., & Chen, S. (2025). Scalable Graph Coloring Optimization Based on Spark GraphX Leveraging Partition Asymmetry. Symmetry, 17, Article 1177. https://doi.org/10.3390/sym17081177
Tao, P., Aihara, K., & Chen, L. (2026). Brain-Inspired Chaotic Graph Backpropagation for Combinatorial Optimization. IEEE Transactions on Neural Networks and Learning Systems, 37, 3488–3500. https://doi.org/10.1109/TNNLS.2025.3650570
Terci, G. S., & Boz, B. (2025). Coloring Dynamic Graphs with a Similarity and Pool-Based Evolutionary Algorithm. IEEE Access, 13, 38054–38075. https://doi.org/10.1109/ACCESS.2025.3546108
Vanderbush, K., & Weber, M. (2026). Neural Algorithmic Reasoning for Approximate k-Coloring with Recursive Warm Starts. Machine Learning: Science and Technology, 7. https://doi.org/10.1088/2632-2153/ae6f6e
Wang, X., Yan, X., & Jin, Y. (2024). A Graph Neural Network with Negative Message Passing and Uniformity Maximization for Graph Coloring. Complex & Intelligent Systems, 10, 4445–4455. https://doi.org/10.1007/s40747-024-01355-w
Yakut, S., & Karagöz, E. (2025). A Graph-Theoretic Solution to NP-Complete Sudoku Puzzles: Malatya Centrality for Large-Scale Optimization. IEEE Access, 13, 182737–182750. https://doi.org/10.1109/ACCESS.2025.3622191
Yusak, M. Y., Putri, D. F., & Syaripuddin, S. (2024). Penerapan Pewarnaan Graf Menggunakan Algoritma Welch-Powell pada Penjadwalan Mata Pelajaran: Studi Kasus Penjadwalan Mata Pelajaran SMP Terpadu Rea Kaltim Kembang Janggut. Journal of Mathematics Education and Science, 7(2), 177–183. https://doi.org/10.32665/james.v7i2.2272
Zhu, E., Zhang, Y., Sun, H., Wei, Z., Pedrycz, W., Liu, C., & Xu, J. (2025). HyColor: An Efficient Heuristic Algorithm for Graph Coloring. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 56, 681–695. https://doi.org/10.1109/TSMC.2025.3629990
