Hostname: page-component-745bb68f8f-f46jp Total loading time: 0 Render date: 2025-02-07T02:59:18.952Z Has data issue: false hasContentIssue false
  • English
  • Français

List Colourings of Regular Hypergraphs

Published online by Cambridge University Press:  02 February 2012

DAVID SAXTON  and
ANDREW THOMASON
DAVID SAXTON
Affiliation:
DPMMS, Centre for Mathematical Sciences, Wilberforce Road, Cambridge, UK (e-mail: D.W.Saxton@dpmms.cam.ac.uk, A.G.Thomason@dpmms.cam.ac.uk)
ANDREW THOMASON
Affiliation:
DPMMS, Centre for Mathematical Sciences, Wilberforce Road, Cambridge, UK (e-mail: D.W.Saxton@dpmms.cam.ac.uk, A.G.Thomason@dpmms.cam.ac.uk)
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.

We show that the list chromatic number of a simple d-regular r-uniform hypergraph is at least (1/2r log(2r2) + o(1)) log d if d is large.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 21 , Issue 1-2: Honouring the Memory of Richard H. Schelp , March 2012 , pp. 315 - 322
Copyright
Copyright © Cambridge University Press 2012

References

[1]Alon, N. (1993) Restricted colorings of graphs. In Surveys in Combinatorics 1993, Vol. 187 of London Mathematical Society Lecture Notes (Walker, K., ed.), Cambridge University Press, pp. 1–33.Google Scholar
[2]Alon, N. (2000) Degrees and choice numbers. Random Struct. Alg. 16 364–368.3.0.CO;2-0>CrossRefGoogle Scholar
[3]Alon, N. and Kostochka, A. Hypergraph list coloring and Euclidean Ramsey theory. Random Struct. Alg. (to appear).Google Scholar
[4]Alon, N. and Kostochka, A. Dense uniform hypergraphs have high list chromatic number. Discrete Mathematics, (in press).Google Scholar
[5]Erdős, P., Rubin, A. L. and Taylor, H. (1979) Choosability in graphs. In Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium XXVI 125–157.Google Scholar
[6]Haxell, P. and Pei, M. (2009) On list coloring Steiner triple systems. J. Combin. Designs 17 314–322.Google Scholar
[7]Haxell, P. and Verstraëte, J. (2010) List coloring hypergraphs. Electron. J. Combin. 17 #R129.CrossRefGoogle Scholar
[8]Saxton, D. and Thomason, A. In preparation.Google Scholar
[9]Vizing, V. G. (1976) Coloring the vertices of a graph in prescribed colors (in Russian). Diskret. Anal. 29 3–10.Google Scholar