Research for the Impact of Vertex Count and Edge Density on the Chromatic Number of Random Graphs

This study investigates the relationship between the chromatic number, edge density, and vertex count in random graphs. Using the Erdős–Rényi model, 750 random graphs G(n,p) were generated with varying n and p, and their chromatic numbers were estimated using a greedy algorithm. Results revealed a linear increase in chromatic number with vertex count, while edge density exhibited a nonlinear influence. Two regression models, full and simplified, were developed to predict chromatic numbers effectively. The simplified model demonstrated higher efficiency and comparable accuracy, providing valuable insights into graph coloring. These findings have practical implications for scheduling, resource allocation, and network optimization, addressing key challenges in real-world applications. Additionally, this research offers a foundation for further exploration into advanced graph models and optimization strategies, contributing to theoretical advancements and practical problem-solving in computational and applied graph theory.