This article is cited 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$.

UDC: 519.11

Received: 19.12.2008

DOI: 10.4213/dm1110

 English version: Discrete Mathematics and Applications, 2010, 20:4, 391–409

Bibliographic databases:

• 
• 
• 
•