Paper Title
A Comparative Study of Vertex Ordering Heuristics in Greedy Graph Coloring Across Varying Graph Densities

Abstract
Graph coloring is a classical NP-hard problem with applications in scheduling, register allocation, and frequency assignment. The Greedy Graph Coloring algorithm is computationally efficient but highly sensitive to vertex ordering. This study presents a comparative analysis of Natural Ordering (NO), Largest Degree First (LDF), Smallest Degree First (SDF), and Random Ordering (RO) across graphs of varying densities. Experimental results show that Largest Degree First significantly reduces color usage, particularly in dense graphs, while maintaining acceptable computational overhead. Keywords - Graph Coloring, Greedy Algorithm, Vertex Ordering, Heuristics, Graph Density