Cover-Decomposition and Polychromatic Numbers

DOI10.1007/978-3-642-23719-5_67zbMath1346.05059arXiv1009.6144OpenAlexW1881309395WikidataQ101130566 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

hypergraphsprobabilistic methodsgeometric hypergraphspolychromatic numbercover-decomposition numberiterated linear programming relaxationpolychromatic vertex coloring

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

Polychromatic colorings of hypergraphs with high balance ⋮ Polychromatic colorings of 1-regular and 2-regular subgraphs of complete graphs ⋮ Unsplittable coverings in the plane ⋮ A note on the discrepancy of matrices with bounded row and column sums ⋮ Coloring Delaunay-edges and their generalizations ⋮ Polychromatic colorings and cover decompositions of hypergraphs ⋮ A note on homomorphisms of Kneser hypergraphs ⋮ Colouring non-even digraphs ⋮ Hardness of Rainbow Coloring Hypergraphs

This page was built for publication: Cover-Decomposition and Polychromatic Numbers