Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-27T09:10:53.434Z 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: [email protected])
A. V. KOSTOCHKA
Affiliation:
Department of Mathematics, University of Illinois, Urbana, IL 61801, USA and Institute of Mathematics, Novosibirsk, 630090, Russia (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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