PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2003 | 23 | 2 | 207-213
Tytuł artykułu

Hajós' theorem for list colorings of hypergraphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Słowa kluczowe
Wydawca
Rocznik
Tom
23
Numer
2
Strony
207-213
Opis fizyczny
Daty
wydano
2003
otrzymano
2001-10-23
poprawiono
2002-05-22
Twórcy
  • Université Joseph Fourier - Laboratorie Leibniz, 46 avenue Félix Viallet, 38031 Grenoble Cedex 9, France
  • CNRS - GeoD research group, Laboratoire Leibniz, 46 avenue Félix Viallet, 38031 Grenoble Cedex 9, France
  • Department of Mathematics, University of Ljubljana, Jadranska 19, 1111 Ljubljana, Slovenia
  • 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
Bibliografia
  • [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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1197
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.