The existence of panchromatic colourings for uniform hypergraphs
Sbornik. Mathematics, Tome 201 (2010) no. 4, pp. 607-630
Voir la notice de l'article provenant de la source Math-Net.Ru
The well-known extremal problem concerning panchromatic colouring of hypergraphs is investigated. An $r$-colouring of the set of vertices of a hypergraph is said to be panchromatic if each link of the hypergraph is incident to vertices of all colours. The quantity $p(n,r)$ defined as the minimum number of links in an $n$-uniform hypergraph which admits no panchromatic $r$-colourings is studied. New lower and upper bounds for
$p(n,r)$ are obtained, which improve earlier results for many of the relations between the parameters $n$ and $r$. In addition, a sufficient condition for the existence of a panchromatic $r$-colouring of an $n$-uniform hypergraph is obtained.
Bibliography: 18 items.
Keywords:
hypergraph, panchromatic colouring, the method of random colouring.
@article{SM_2010_201_4_a5,
author = {D. A. Shabanov},
title = {The existence of panchromatic colourings for uniform hypergraphs},
journal = {Sbornik. Mathematics},
pages = {607--630},
publisher = {mathdoc},
volume = {201},
number = {4},
year = {2010},
language = {en},
url = {http://geodesic.mathdoc.fr/item/SM_2010_201_4_a5/}
}
D. A. Shabanov. The existence of panchromatic colourings for uniform hypergraphs. Sbornik. Mathematics, Tome 201 (2010) no. 4, pp. 607-630. http://geodesic.mathdoc.fr/item/SM_2010_201_4_a5/