Every graph with 
vertices and maximum vertex
degree 
is 
-colorable
with all color classes of size 
or ![[n/(k+1)]](/images/equations/Hajnal-SzemerediTheorem/Inline5.svg)
, where 
is the floor function
and ![[x]](/images/equations/Hajnal-SzemerediTheorem/Inline7.svg)
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