Cover-Decomposition and Polychromatic Numbers

DOI10.1007/978-3-642-23719-5_67zbMath1346.05059arXiv1009.6144WikidataQ101130566 ScholiaQ101130566MaRDI QIDQ3092281

No author found.

Publication date: 16 September 2011

Published in: SIAM Journal on Discrete Mathematics, Algorithms – ESA 2011 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1009.6144

zbMATH Keywords

hypergraphs; probabilistic methods; geometric hypergraphs; polychromatic number; cover-decomposition number; iterated linear programming relaxation; polychromatic vertex coloring

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

05C65: Hypergraphs

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)