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

Xueer Wang

doi:10.54097/2w5wq019

Authors

Xueer Wang

DOI:

https://doi.org/10.54097/2w5wq019

Keywords:

chromatic number, random graphs, edge density, greedy algorithm, regression modeling.

Abstract

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.

Downloads

Download data is not yet available.

References

[1] Erdős P., Rényi A. On random graphs. Publicationes Mathematicae, 1959, 6: 290–297.

[2] Bollobás B. Random Graphs. In: Modern Graph Theory. Graduate Texts in Mathematics, vol 184. Springer, New York, NY, 1998.

[3] Barabási A.-L., Albert R. Emergence of scaling in random networks. Science, 1999, 286(5439): 509–512.

[4] Daudin J. J., Picard F., Robin S. A mixture model for random graphs. Stat Comput, 2008, 18: 173–183. https://doi.org/10.1007/s11222-007-9046-7.

[5] Diestel R. Graph Theory (5th ed.). Springer, 2017.

[6] Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (3rd ed.). MIT Press, 2009.

[7] Behzad M. Graphs and Their Chromatic Numbers. (Order No. 6606101). ProQuest Dissertations & Theses Global, 1965.

[8] Holland P. W., Laskey K. B., Leinhardt S. Stochastic blockmodels: First steps. Social Networks, 1983, 5(2): 109–137.

[9] Welsh D. J. A., Powell M. B. An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal, 1967, 10(1): 85–86.

[10] Smith J., Taylor A. Advances in graph coloring algorithms. Journal of Graph Algorithms and Applications, 2020, 24(2): 133–155.

[11] Zhang L., Chen Y. Chromatic number estimation in stochastic graphs. Computational Graph Theory, 2021, 37(4): 455–472.

[12] Lee K., Park H., Kim J. Efficient algorithms for graph coloring in dense networks. Journal of Computational Mathematics, 2022, 58(3): 487–499.