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

Abstract

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

How to cite

top

Claude 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. [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. [2] C. Benzaken, Hajós' theorem for hypergraphs, Annals of Discrete Math. 17 (1983) 53-77. 
  3. [3] P. Erdős, A.L. Rubin, and H. Taylor, Choosability in graphs, Congr. Numer. 26 (1980) 122-157. Zbl0469.05032
  4. [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. [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. [6] B. Mohar, Hajós theorem for colorings of edge-weighted graphs, manuscript, 2001. 
  7. [7] V.G. Vizing, Colouring the vertices of a graph in prescribed colours (in Russian), Diskret. Anal. 29 (1976) 3-10. 
  8. [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 ?

top

You must be logged in to post comments.