About dependence of the number of edges and vertices in hypergraph clique with chromatic number 3

MaRDI QIDQ6228242zbMATH OpenFDO

Authors Danila Cherkashin, A. B. Kulikov, Andrei M. Raigorodskii

Publication date 8 October 2011

Abstract: In 1973 P. ErdH{o}s and L. Lov'asz noticed that any hypergraph whose edges are pairwise intersecting has chromatic number 2 or 3. In the first case, such hypergraph may have any number of edges. However, ErdH{o}s and Lov'asz proved that in the second case, the number of edges is bounded from above. For example, if a hypergraph is $n$-uniform, has pairwise intersecting edges, and has chromatic number 3, then the number of its edges does not exceed $n^n$. Recently D.D. Cherkashin improved this bound (see cite{Ch}). In this paper, we further improve it in the case when the number of vertices of an $n$-uniform hypergraph is bounded from above by $n^m$ with some $m=m(n)$.

This page was built for publication: About dependence of the number of edges and vertices in hypergraph clique with chromatic number 3

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6228242)