This article is cited in 5 scientific papers (total in 5 papers)
The existence of panchromatic colourings for uniform hypergraphs
D. A. Shabanov
M. V. Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
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.
hypergraph, panchromatic colouring, the method of random colouring.
PDF file (580 kB)
Sbornik: Mathematics, 2010, 201:4, 607–630
MSC: Primary 05C15; Secondary 05C65
D. A. Shabanov, “The existence of panchromatic colourings for uniform hypergraphs”, Mat. Sb., 201:4 (2010), 137–160; Sb. Math., 201:4 (2010), 607–630
Citation in format AMSBIB
\paper The existence of panchromatic colourings for uniform hypergraphs
\jour Mat. Sb.
\jour Sb. Math.
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
Shabanov D.A., “On a generalization of Rubin's theorem”, J. Graph Theory, 67:3 (2011), 226–234
A. P. Rozovskaya, D. A. Shabanov, “Improvement of the Lower Bound in the Kostochka Problem of Panchromatic Coloring of a Hypergraph”, Math. Notes, 89:6 (2011), 903–906
A. M. Raigorodskii, D. A. Shabanov, “The Erdős–Hajnal problem of hypergraph colouring, its generalizations, and related problems”, Russian Math. Surveys, 66:5 (2011), 933–1002
A. P. Rozovskaya, D. A. Shabanov, “Extremal problems for panchromatic colourings of uniform hypergraphs”, Discrete Math. Appl., 22:2 (2012), 185–206
Kang R.J., “Improper Choosability and Property B”, J. Graph Theory, 73:3 (2013), 342–353
|Number of views:|