|
This article is cited in 3 scientific papers (total in 3 papers)
On proper colourings of hypergraphs using prescribed colours
A. P. Rozovskaya, D. A. Shabanov
Abstract:
We consider a generalisation of the classic combinatorial problem of P. Erdős and A. Hajnal in the theory of hypergraphs to the case of prescribed colourings. We investigate the value $m_{pr}(n,r)$ equal to the minimum number of edges of a hypergraph in the class of $n$-uniform hypergraphs with prescribed chromatic number greater than $r$. We obtain a lower bound for this value which is better than the known results for $r\ge3$. Moreover, we give a sufficient conditions for existence of a prescribed $r$-colourability of an $n$-uniform hypergraph in terms of restrictions on the intersections of edges. As a corollary we obtain a new bound for the characteristic $m_{pr}^*(n,r)$ equal to the minimum number of edges of a hypergraph in the class of $n$-uniform simple hypergraphs (in which any two edges have at most one common vertex) with the prescribed chromatic number greater than $r$.
Received: 19.12.2008
Citation:
A. P. Rozovskaya, D. A. Shabanov, “On proper colourings of hypergraphs using prescribed colours”, Diskr. Mat., 22:3 (2010), 94–109; Discrete Math. Appl., 20:4 (2010), 391–409
Linking options:
https://www.mathnet.ru/eng/dm1110https://doi.org/10.4213/dm1110 https://www.mathnet.ru/eng/dm/v22/i3/p94
|
Statistics & downloads: |
Abstract page: | 611 | Full-text PDF : | 191 | References: | 62 | First page: | 12 |
|