A note on a list colouring of hypergraphs

• Autorzy: Drgas-Burchardt E.
• Języki publikacji: EN

Abstrakty

EN

In the note we present two results. The first of them gives a sufficient condition for a colouring of a hypergraph from an assigned list. It generalises the analogous fact for graphs. The second result states that for every k ≥ 3 and every l ≥ 2, a distance between the list chromatic number and the chromatic number can be arbitrarily large in the class of k-uniform hypergraphs with the chromatic number bounded below by l. A similar result for k-uniform, 2-colorable hypergraphs is known but the proof techniques are different.

Słowa kluczowe

EN

hypergraph; list colouring

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2004
• Tom: Vol. 24, no. 2
• Strony: 171--175
• Opis fizyczny: Bibliogr. 6 poz.

Twórcy

autor

Drgas-Burchardt E.

• University of Zielona Góra, Faculty of Mathematics Computer Science and Econometrics, ul. Podgórna 50, 65-246 Zielona Góra, Poland,

Bibliografia

• [1] Borowiecki M., Drgas-Burchardt E., Mihók P.: Generalized list colourings of graphs. Discussiones Mathematicae Graph Theory 15 (2) (1995), 185-193.
• [2] Erdos P., Lovasz L.: Problems and results on 3-chromatic hypergraphs and some related questions. Colloquia Mathematica Societatis Janos Bolai 10, Infinite and Finite Sets, vol. II (1973) 609-627.
• [3] Erdos P., Rubin A. L., Taylor H.: Choosability in graphs, in: Proceedings West Coast Conference on Combinatorics. Graph Theory and Computing, Arcata CA, Sept. 5-7, 1979, Congr. Numer. 26.
• [4] Kostochka A. V., Stiebitz M., Wirth B.: The colour theorems of Brooks and Gallai extended. Discrete Mathematics 162 (1996), 299-303.
• [5] Reed B.: The Ust colouring constants. J. Graph Theory 31 (1999), 149-153.
• [6] Vizing V. G., Colouring the vertices of graph in prescribed colours. Diskret. Analiz. 29, Metody Diskret. Anal, v Teorii Kodov i Shem 101 (1976), 3-10 (Russian).