Around Erdos-Lovasz problem on colorings of non-uniform hypergraphs

作者：Shabanov Dmitry A^*

来源：Discrete Mathematics, 2015, 338(11): 1976-1981.

DOI：10.1016/j.disc.2015.04.017

• Colorings of hypergraphs
• Erdos-Lovasz problem
• Non-uniform hypergraphs
• Probabilistic methods

The work deals with combinatorial problems concerning colorings of non-uniform hypergraphs. Let H = (V, E) be a hypergraph with minimum edge-cardinality n. We show that if H is a simple hypergraph (i.e. every two distinct edges have at most one common vertex) and
(e is an element of E)Sigma r(1-vertical bar e vertical bar) <= c root n,
for some absolute constant c > 0, then H is r-colorable. We also obtain a stronger result for triangle-free simple hypergraphs by proving that if H is a simple triangle-free hypergraph and
(e is an element of E)Sigma r(1-vertical bar e vertical bar) <= c . n,
for some absolute constant c > 0, then H is r-colorable.

• 出版日期2015-11-6