Geodesic
Hajós' theorem for list colorings of hypergraphs
Discussiones Mathematicae. Graph Theory, Tome 23 (2003) no. 2, pp. 207-213.

Voir la notice de l'article provenant de la source Library of Science

A well-known theorem of Hajós claims that every graph with chromathic number greater than k can be constructed from disjoint copies of the complete graph K_k+1 by repeated application of three simple operations. This classical result has been extended in 1978 to colorings of hypergraphs by C. Benzaken and in 1996 to list-colorings of graphs by S. Gravier. In this note, we capture both variations to extend Hajós' theorem to list-colorings of hypergraphs.
Keywords: list-coloring, Hajós' construction, hypergraph 
@article{DMGT_2003_23_2_a0,
     author = {Benzaken, Claude and Gravier, Sylvain and Skrekovski, Riste},
     title = {Haj\'os' theorem for list colorings of hypergraphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {207--213},
     publisher = {mathdoc},
     volume = {23},
     number = {2},
     year = {2003},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2003_23_2_a0/}
}
TY  - JOUR
AU  - Benzaken, Claude
AU  - Gravier, Sylvain
AU  - Skrekovski, Riste
TI  - Hajós' theorem for list colorings of hypergraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2003
SP  - 207
EP  - 213
VL  - 23
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2003_23_2_a0/
LA  - en
ID  - DMGT_2003_23_2_a0
ER  - 
%0 Journal Article
%A Benzaken, Claude
%A Gravier, Sylvain
%A Skrekovski, Riste
%T Hajós' theorem for list colorings of hypergraphs
%J Discussiones Mathematicae. Graph Theory
%D 2003
%P 207-213
%V 23
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2003_23_2_a0/
%G en
%F DMGT_2003_23_2_a0
Benzaken, Claude; Gravier, Sylvain; Skrekovski, Riste. Hajós' theorem for list colorings of hypergraphs. Discussiones Mathematicae. Graph Theory, Tome 23 (2003) no. 2, pp. 207-213. http://geodesic.mathdoc.fr/item/DMGT_2003_23_2_a0/

[1] C. Benzaken, Post's closed systems and the weak chromatic number of hypergraphs, Discrete Math. 23 (1978) 77-84, doi: 10.1016/0012-365X(78)90106-1.

[2] C. Benzaken, Hajós' theorem for hypergraphs, Annals of Discrete Math. 17 (1983) 53-77.

[3] P. Erdős, A.L. Rubin, and H. Taylor, Choosability in graphs, Congr. Numer. 26 (1980) 122-157.

[4] S. Gravier, A Hajós-like theorem for list colorings, Discrete Math. 152 (1996) 299-302, doi: 10.1016/0012-365X(95)00350-6.

[5] G. Hajós, Über eine Konstruktion nicht n-färbbarer Graphen, Wiss. Z. Martin Luther Univ. Math.-Natur. Reihe 10 (1961) 116-117.

[6] B. Mohar, Hajós theorem for colorings of edge-weighted graphs, manuscript, 2001.

[7] V.G. Vizing, Colouring the vertices of a graph in prescribed colours (in Russian), Diskret. Anal. 29 (1976) 3-10.

[8] X. Zhu, An analogue of Hajós's theorem for the circular chromatic number, Proc. Amer. Math. Soc. 129 (2001) 2845-2852, doi: 10.1090/S0002-9939-01-05908-1.