Every graph with vertices and maximum vertex degree is -colorable with all color classes of size or , where is the floor function and is the ceiling function.
Hajnal-Szemerédi Theorem
See also
Seymour ConjectureExplore with Wolfram|Alpha
References
Hajnal, A. and Szemerédi, E. "Proof of a Conjecture of Erdős." In Combinatorial Theory and Its Applications, Vol. 2 (Ed. P. Erdős, A. Rényi, and V. T. Sós). Amsterdam, Netherlands: North-Holland, pp. 601-623, 1970.Komlós, J.; Sárkőzy, G. N.; and Szemerédi, E. "Proof of the Seymour Conjecture for Large Graphs." Ann. Comb. 2, 43-60, 1998.Referenced on Wolfram|Alpha
Hajnal-Szemerédi TheoremCite this as:
Weisstein, Eric W. "Hajnal-Szemerédi Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Hajnal-SzemerediTheorem.html