A. E. Khuzieva, D. A. Shabanov, “On regular hypergraphs with high girth and high chromatic number”, Diskr. Mat., 2015, Volume 27, Issue 2,Pages <nobr>112

This article is cited in 2 papers

On regular hypergraphs with high girth and high chromatic number

A. E. Khuzieva^a, D. A. Shabanov^b

^a Moscow Institute of Physics and Technology (State University), Dolgoprudny, Moscow region
^b Lomonosov Moscow State University

Abstract: The paper is concerned with an extremal problem of combinatorial analysis on finding the minimal possible number of edges in an $n$-regular hypergraph with chromatic number greater than $r$ and girth greater than $s$. A new lower estimate of this extremal value is obtained and a number of related results is proved.

Keywords: hypergraph, colouring of hypergraphs, sparse hypergraphs, random recolouring method, girth of a hypergraph.

UDC: 519.112.7, 519.179.1, 519.179.4

Received: 06.04.2015

DOI: 10.4213/dm1329