ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


M. Axenovich and A. Karrer


High girth hypergraphs with unavoidable monochromatic or rainbow edges


Discussiones Mathematicae Graph Theory

Received: 2019-07-12, Revised: 2019-11-27, Accepted: 2019-11-29,


A classical result of Erdős and Hajnal claims that for any integers $k, r, g \geq 2$ there is an $r$-uniform hypergraph of girth at least $g$ with chromatic number at least $k$. This implies that there are sparse hypergraphs such that in any coloring of their vertices with at most $k-1$ colors there is a monochromatic hyperedge. When there is no restriction on the number of the colors used, one can easily avoid monochromatic hyperedges. Then, however, so-called rainbow or multicolored hyperedges might appear. Nešetřil and Rödl \cite{NR-sel} called hypergraphs such that in any vertex-coloring there is either a monochromatic or a rainbow hyperedge, selective. They showed an existence of selective $r$-uniform hypergraphs of girth $g$ for any integers $r, g\geq 2$ using probabilistic and explicit constructions. In this paper, we provide a slightly different construction of such hypergraphs and summarize the probabilistic approaches. The main building block of the construction, a part-rainbow-forced hypergraph, is of independent interest. This is an $r$-uniform $r$-partite hypergraph with a given girth such that in any vertex-coloring that is rainbow on each part, there is a rainbow hyperedge. We give a simple construction of such a hypergraph that does not use iterative amalgamation.


hypergraph, chromatic number, mixed hypergraph, bihypergraphs, monochromatic, rainbow, girth, selective