Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-15T01:58:17.522Z Has data issue: false hasContentIssue false
  • English
  • Français

A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring

Published online by Cambridge University Press:  01 March 2008

H. A. KIERSTEAD and
A. V. KOSTOCHKA
H. A. KIERSTEAD
Affiliation:
Department of Mathematics and Statistics, Arizona State University, Tempe, AZ 85287, USA (e-mail: kierstead@asu.edu)
A. V. KOSTOCHKA
Affiliation:
Department of Mathematics, University of Illinois, Urbana, IL 61801, USA and Institute of Mathematics, Novosibirsk, 630090, Russia (e-mail: kostochk@math.uiuc.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

A proper vertex colouring of a graph is equitable if the sizes of colour classes differ by at most one. We present a new shorter proof of the celebrated Hajnal–Szemerédi theorem: for every positive integer r, every graph with maximum degree at most r has an equitable colouring with r+1 colours. The proof yields a polynomial time algorithm for such colourings.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 17 , Issue 2 , March 2008, pp. 265 - 270
Copyright
Copyright © Cambridge University Press 2007

References

[1]Blazewicz, J., Ecker, K., Pesch, E., Schmidt, G. and Weglarz, J. (2001) Scheduling Computer and Manufacturing Processes, 2nd edn, Springer.CrossRefGoogle Scholar
[2]Chen, B.-L., Lih, K.-W. and Wu, P.-L. (1994) Equitable coloring and the maximum degree. Europ. J. Combin. 15 443–447.CrossRefGoogle Scholar
[3]Erdős, P. (1964) Problem 9. In Theory of Graphs and its Applications (Fiedler, M., ed.), Czech. Academy of Sciences, Prague, p. 159.Google Scholar
[4]Fan, G. and Kierstead, H. A. (1996) Hamiltonian square paths. J. Combin. Theory Ser. B 67 167–182.CrossRefGoogle Scholar
[5]Hajnal, A. and Szemerédi, E. (1970) Proof of a conjecture of P. Erdős. In Combinatorial Theory and its Application (Erdős, P., Rényi, A., and Sós, V. T., eds), North-Holland, London, pp. 601–623.Google Scholar
[6]Janson, S. and Ruciński, A. (2002) The infamous upper tail. Random Struct. Alg. 20 317–342.CrossRefGoogle Scholar
[7]Komlós, J., Sárkőzy, G. and Szemerédi, E. (1998) Proof of the Seymour conjecture for large graphs. Ann. Combin. 1 43–60.CrossRefGoogle Scholar
[8]Kostochka, A. V., Pelsmajer, M. J. and West, D. B. (2003) A list analogue of equitable coloring. J. Graph Theory 44 166–177.CrossRefGoogle Scholar
[9]Kostochka, A. V. and Yu, G. (2006) Extremal problems on packing of graphs. Oberwolfach Reports 1 55–57.Google Scholar
[10]Kostochka, A. V. and Yu, G. (2007) Ore-type graph packing problems. Combin. Probab. Comput. 16 167–169.CrossRefGoogle Scholar
[11]Mydlarz, M. and Szemerédi, E. Algorithmic Brooks' theorem. Manuscript.Google Scholar
[12]Ore, O. (1960) Note on Hamilton circuits. Amer. Math. Monthly 67 55.CrossRefGoogle Scholar
[13]Pemmaraju, S. V. (2001) Equitable colorings extend Chernoff–Hoeffding bounds. In Proc. 5th International Workshop on Randomization and Approximation Techniques in Computer Science (APPROX-RANDOM 2001), pp. 285–296.CrossRefGoogle Scholar
[14]Seymour, P. (1974) Problem section. In Combinatorics: Proc. British Combinatorial Conference 1973 (McDonough, T. P. and Mavron, V. C., eds), Cambridge University Press, pp. 201–202.Google Scholar
[15]Smith, B. F., Bjorstad, P. E. and Gropp, W. D. (1996) Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations, Cambridge University Press.Google Scholar
[16]Tucker, A. (1973) Perfect graphs and an application to optimizing municipal services. SIAM Review 15 585–590.CrossRefGoogle Scholar