Hypergraph coverings and local colorings
type: Item
instance of: scholarly article
title: Hypergraph coverings and local colorings
zbMATH Open document ID: 0675.05050
DOI: 10.1016/0095-8956(91)90092-X
author: Yair Caro
author: Zsolt Tuza
published in: Journal of Combinatorial Theory. Series B
publication date: 1991-01-01T00:00:00Z
review text: If the edge sets of some r-uniform hypergraphs \b{H}\({}_ 1,...,\underline H_ t\) contain all the r-tuples of an n-element set, and each \b{H}\({}_ i\) has chromatic number at most k, then for the sum of the orders of the \b{H}\({}_ i\) we have \(\sum | V(\underline H_ i)| \geq (n \log (n/r-1))/\log k\). In particular, if \(K^ r_ n\) has an edge coloring such that each vertex is incident to edges of at most s colors and every monochromatic class of edges forms a k-vertex-colorable hypergraph, then \(n\leq (r-1)k^ s\). Both bounds are sharp. The first inequality can be extended for more general weight functions f: \({\mathbb{R}}^+\to {\mathbb{R}}^+\), f convex, f(x)/x decreasing for \(x>0\); in this case \(\sum f(| V(\underline H_ i)|)\geq (f(n)\log (n/r- 1))/\log k.\)
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 4105005
zbMATH Keywords: edge covering
zbMATH Keywords: weighted covering
zbMATH Keywords: local coloring
zbMATH Keywords: uniform hypergraphs
zbMATH Keywords: chromatic number
MaRDI profile type: Publication
cites work: Local \(k\)-colorings of graphs and hypergraphs
cites work: On a problem of G. O. H. Katona and T. Tarján
cites work: Q5203068
cites work: Q5525916
cites work: Linear upper bounds for local Ramsey numbers
cites work: Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices
cites work: Q5750908
cites work: Inequalities for two set systems with prescribed intersections
full work available at URL: 0095-8956(91)90092-x
OpenAlex ID: W2060698513
description: scientific article; zbMATH DE number 4105005