- Tytuł:
- High Girth Hypergraphs with Unavoidable Monochromatic or Rainbow Edges
- Autorzy:
-
Axenovich, Maria
Karrer, Annette - Powiązania:
- https://bibliotekanauki.pl/articles/32361723.pdf
- Data publikacji:
- 2022-05-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
hypergraph
chromatic number
mixed hypergraph
bihyper-graphs
monochromatic
rainbow
girth
selective - Opis:
- A classical result of Erdős and Hajnal claims that for any integers k, r, g ≥ 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 [19] 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 ≥ 2 using probabilistic and explicit constructions. In this paper, we provide a slightly di erent 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2022, 42, 2; 471-484
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł