Covering complete hypergraphs with cuts of minimum total size

DOI10.1007/s00373-011-1030-5zbMath1234.05171OpenAlexW2095539279MaRDI QIDQ659756

Sebastian M. Cioabă, André Kündgen

Publication date: 24 January 2012

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-011-1030-5

zbMATH Keywords

hypergraphcutcover2-Colorable

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15)

Related Items

On the biclique cover of the complete graph ⋮ On the decomposition of random hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Separating systems and oriented graphs of diameter two
• On separating systems
• On shortest cocycle covers of graphs
• On embedding complete graphs into hypercubes
• A bound on the total size of a cut cover
• On the Size of Separating Systems and Families of Perfect Hash Functions
• Chromatic numbers of hypergraphs and coverings of graphs
• An application of graph coloring to printed circuit testing
• The biparticity of a graph
• On separating systems of a finite set
• k-Components, Clusters and Slicings in Graphs
• Covering a graph with cuts of minimum total size