DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 23(2) (2003) 207-213
DOI: https://doi.org/10.7151/dmgt.1197

HAJÓS' THEOREM FOR LIST COLORINGS OF HYPERGRAPHS1

Claude Benzaken

Université Joseph Fourier - Laboratorie Leibniz
46 avenue Félix Viallet
38031 Grenoble Cedex 9, France
e-mail: Claude.Benzaken@imag.fr

Sylvain Gravier

CNRS - GeoD research group, Laboratoire Leibniz
46 avenue Félix Viallet
38031 Grenoble Cedex 9, France
e-mail: Sylvain.Gravier@imag.fr

Riste Skrekovski2

Department of Mathematics
University of Ljubljana
Jadranska 19, 1111 Ljubljana, Slovenia
e-mail: skreko@fmf.uni-lj.si
and 
Charles University, Faculty of Mathematics and Physics
DIMATIA and Institute for Theoretical Computer Science (ITI) 3
Malostranské nám. 2/25, 118 00, Prague, Czech Republic
e-mail: skreko@kam.mff.cuni.cz

Abstract

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 Kk+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.

2000 Mathematics Subject Classification: 05C15, 05C99.

References

[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.

Received 23 October 2001
Revised 22 May 2002

 

Footnotes:

1This research was partially supported by the PROTEUS Project 00874RL.
2Supported in part by the Ministry of Science and Technology of Slovenia, Research Project Z1-3129.
3Supported in part by the Ministry of Education of Czech Republic, Project LN00A056.

Close