# Hajós' theorem for list colorings of hypergraphs

Claude Benzaken; Sylvain Gravier; Riste Skrekovski

Discussiones Mathematicae Graph Theory (2003)

- Volume: 23, Issue: 2, page 207-213
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topClaude Benzaken, Sylvain Gravier, and Riste Skrekovski. "Hajós' theorem for list colorings of hypergraphs." Discussiones Mathematicae Graph Theory 23.2 (2003): 207-213. <http://eudml.org/doc/270536>.

@article{ClaudeBenzaken2003,

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 $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.},

author = {Claude Benzaken, Sylvain Gravier, Riste Skrekovski},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {list-coloring; Hajós' construction; hypergraph; list coloring; Hajós’ theorem},

language = {eng},

number = {2},

pages = {207-213},

title = {Hajós' theorem for list colorings of hypergraphs},

url = {http://eudml.org/doc/270536},

volume = {23},

year = {2003},

}

TY - JOUR

AU - Claude Benzaken

AU - Sylvain Gravier

AU - Riste Skrekovski

TI - Hajós' theorem for list colorings of hypergraphs

JO - Discussiones Mathematicae Graph Theory

PY - 2003

VL - 23

IS - 2

SP - 207

EP - 213

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

LA - eng

KW - list-coloring; Hajós' construction; hypergraph; list coloring; Hajós’ theorem

UR - http://eudml.org/doc/270536

ER -

## References

top- [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. Zbl0397.05038
- [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. Zbl0469.05032
- [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. Zbl0853.05037
- [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. Zbl0971.05042

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.