TOPICS
Search

Hajnal-Szemerédi Theorem


Every graph with n vertices and maximum vertex degree Delta(G)<=k is (k+1)-colorable with all color classes of size |_n/(k+1)_| or [n/(k+1)], where |_x_| is the floor function and [x] is the ceiling function.


See also

Seymour Conjecture

Explore 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 Theorem

Cite this as:

Weisstein, Eric W. "Hajnal-Szemerédi Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Hajnal-SzemerediTheorem.html

Subject classifications