Download PDF - Hajós' theorem for list colorings of hypergraphsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Hajós' theorem for list colorings of hypergraphs

Authors 1, 2, 3, 4

Affiliations

  1. Université Joseph Fourier - Laboratorie Leibniz, 46 avenue Félix Viallet, 38031 Grenoble Cedex 9, France
  2. CNRS - GeoD research group, Laboratoire Leibniz, 46 avenue Félix Viallet, 38031 Grenoble Cedex 9, France
  3. Department of Mathematics, University of Ljubljana, Jadranska 19, 1111 Ljubljana, Slovenia
  4. Charles University, Faculty of Mathematics and Physics, DIMATIA and Institute for Theoretical Computer Science (ITI), Malostranské nám. 2/25, 118 00, Prague, Czech Republic

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

ENG
list-coloring, Hajós' construction, hypergraph

Bibliography

  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.
Discussiones Mathematicae Graph Theory
2003/23/2
Export to PBN, Opens in new tab
Pages:
207-213
Main language of publication
English
Received
2001-10-23
Accepted
2002-05-22
Published
2003

DOI: 10.7151/dmgt.1197

Exact and natural sciences